From: Antonio Quartulli antonio@open-mesh.com

In the current implementation the first OGM is scheduled when a new hard-interface is enabled, no matter if it is active (thus ready for sending packets) or not.

However, the B.A.T.M.A.N. IV OGM scheduling mechanism works in a way that reschedules the task forever even if the interface is not yet ready and therefore everything works as expected.

Unfortunately this behaviour is not fine in general and other algorithms may pretend the interface to be active before scheduling the first OGM.

Change this behaviour by scheduling the first OGM upon interface activation.

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- hard-interface.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/hard-interface.c b/hard-interface.c index b851cc5..2a04130 100644 --- a/hard-interface.c +++ b/hard-interface.c @@ -320,6 +320,8 @@ batadv_hardif_activate_interface(struct batadv_hard_iface *hard_iface)

batadv_update_min_mtu(hard_iface->soft_iface);

+ /* begin scheduling originator messages on that interface */ + batadv_schedule_bat_ogm(hard_iface); out: if (primary_if) batadv_hardif_free_ref(primary_if); @@ -459,9 +461,6 @@ int batadv_hardif_enable_interface(struct batadv_hard_iface *hard_iface, "Not using interface %s (retrying later): interface not active\n", hard_iface->net_dev->name);

- /* begin scheduling originator messages on that interface */ - batadv_schedule_bat_ogm(hard_iface); - out: return 0;

From: Linus Luessing linus.luessing@web.de

The B.A.T.M.A.N. protocol originally only used a single message type (called OGM) to determine the link qualities to the direct neighbors and spreading these link quality information through the whole mesh. This procedure is summarized on the BATMAN concept page and explained in details in the RFC draft published in 2008.

This approach was chosen for its simplicity during the protocol design phase and the implementation. However, it also bears some drawbacks:

* Wireless interfaces usually come with some packet loss, therefore a higher broadcast rate is desirable to allow a fast reaction on flaky connections. Other interfaces of the same host might be connected to Ethernet LANs / VPNs / etc which rarely exhibit packet loss would benefit from a lower broadcast rate to reduce overhead. * It generally is more desirable to detect local link quality changes at a faster rate than propagating all these changes through the entire mesh (the far end of the mesh does not need to care about local link quality changes that much). Other optimizations strategies, like reducing overhead, might be possible if OGMs weren't used for all tasks in the mesh at the same time.

As a result detecting local link qualities shall be handled by an independent message type, ELP, whereas the OGM message type remains responsible for flooding the mesh with these link quality information and determining the overall path transmit qualities.

Developed by Linus during a 6 months trainee study period in Ascom (Switzerland) AG.

Signed-off-by: Linus Luessing linus.luessing@web.de Signed-off-by: Marek Lindner lindner_marek@yahoo.de Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- Makefile | 2 + Makefile.kbuild | 2 + README.external | 1 + bat_algo.h | 15 ++++- bat_v.c | 65 ++++++++++++++++++ bat_v_elp.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++++ bat_v_elp.h | 30 +++++++++ gen-compat-autoconf.sh | 1 + main.c | 1 + packet.h | 25 +++++++ types.h | 18 +++++ 11 files changed, 338 insertions(+), 1 deletion(-) create mode 100644 bat_v.c create mode 100644 bat_v_elp.c create mode 100644 bat_v_elp.h

diff --git a/Makefile b/Makefile index 9a7cbae..405175d 100644 --- a/Makefile +++ b/Makefile @@ -25,6 +25,8 @@ export CONFIG_BATMAN_ADV_BLA=y export CONFIG_BATMAN_ADV_DAT=y # B.A.T.M.A.N network coding (catwoman): export CONFIG_BATMAN_ADV_NC=n +# B.A.T.M.A.N. V routing algorithm (experimental): +# export CONFIG_BATMAN_ADV_BATMAN_V=y

PWD:=$(shell pwd) KERNELPATH ?= /lib/modules/$(shell uname -r)/build diff --git a/Makefile.kbuild b/Makefile.kbuild index 42df18f..ae9a6ca 100644 --- a/Makefile.kbuild +++ b/Makefile.kbuild @@ -18,6 +18,8 @@

obj-$(CONFIG_BATMAN_ADV) += batman-adv.o batman-adv-y += bat_iv_ogm.o +batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v.o +batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v_elp.o batman-adv-y += bitarray.o batman-adv-$(CONFIG_BATMAN_ADV_BLA) += bridge_loop_avoidance.o batman-adv-y += debugfs.o diff --git a/README.external b/README.external index c8eac1a..6f0d18b 100644 --- a/README.external +++ b/README.external @@ -39,6 +39,7 @@ module). Available options and their possible values are * CONFIG_BATMAN_ADV_BLA=[y*|n] (B.A.T.M.A.N. bridge loop avoidance) * CONFIG_BATMAN_ADV_DAT=[y*|n] (B.A.T.M.A.N. Distributed ARP Table) * CONFIG_BATMAN_ADV_NC=[y|n*] (B.A.T.M.A.N. Network Coding) + * CONFIG_BATMAN_ADV_BATMAN_V=[y|n*] (B.A.T.M.A.N. V routing algorithm)

e.g., debugging can be enabled by

diff --git a/bat_algo.h b/bat_algo.h index 4e49666..7289336 100644 --- a/bat_algo.h +++ b/bat_algo.h @@ -1,6 +1,6 @@ /* Copyright (C) 2011-2014 B.A.T.M.A.N. contributors: * - * Marek Lindner + * Marek Lindner, Antonio Quartulli * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public @@ -20,4 +20,17 @@

int batadv_iv_init(void);

+#ifdef CONFIG_BATMAN_ADV_BATMAN_V + +int batadv_v_init(void); + +#else + +static inline int batadv_v_init(void) +{ + return 0; +} + +#endif /* CONFIG_BATMAN_ADV_BATMAN_V */ + #endif /* _NET_BATMAN_ADV_BAT_ALGO_H_ */ diff --git a/bat_v.c b/bat_v.c new file mode 100644 index 0000000..7247d7f --- /dev/null +++ b/bat_v.c @@ -0,0 +1,65 @@ +/* Copyright (C) 2013-2014 B.A.T.M.A.N. contributors: + * + * Antonio Quartulli + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + */ + +#include "main.h" +#include "bat_algo.h" +#include "bat_v_elp.h" + +static int batadv_v_iface_enable(struct batadv_hard_iface *hard_iface) +{ + return batadv_v_elp_iface_enable(hard_iface); +} + +static void batadv_v_iface_disable(struct batadv_hard_iface *hard_iface) +{ + batadv_v_elp_iface_disable(hard_iface); +} + +static void batadv_v_iface_update_mac(struct batadv_hard_iface *hard_iface) +{ +} + +static void batadv_v_primary_iface_set(struct batadv_hard_iface *hard_iface) +{ + batadv_v_elp_primary_iface_set(hard_iface); +} + +static void batadv_v_ogm_schedule(struct batadv_hard_iface *hard_iface) +{ +} + +static void batadv_v_ogm_emit(struct batadv_forw_packet *forw_packet) +{ +} + +static struct batadv_algo_ops batadv_batman_v __read_mostly = { + .name = "BATMAN_V", + .bat_iface_enable = batadv_v_iface_enable, + .bat_iface_disable = batadv_v_iface_disable, + .bat_iface_update_mac = batadv_v_iface_update_mac, + .bat_primary_iface_set = batadv_v_primary_iface_set, + .bat_ogm_emit = batadv_v_ogm_emit, + .bat_ogm_schedule = batadv_v_ogm_schedule, +}; + + +int __init batadv_v_init(void) +{ + return batadv_algo_register(&batadv_batman_v); +} diff --git a/bat_v_elp.c b/bat_v_elp.c new file mode 100644 index 0000000..45b082b --- /dev/null +++ b/bat_v_elp.c @@ -0,0 +1,179 @@ +/* Copyright (C) 2011-2014 B.A.T.M.A.N. contributors: + * + * Linus Lüssing, Marek Lindner, Antonio Quartulli + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include "main.h" +#include "hard-interface.h" +#include "send.h" +#include "bat_algo.h" +#include "bat_v_elp.h" + +/** + * batadv_v_elp_start_timer - restart timer for ELP periodic work + * @hard_iface: the interface for which the timer has to be reset + */ +static void batadv_v_elp_start_timer(struct batadv_hard_iface *hard_iface) +{ + unsigned int msecs; + + msecs = atomic_read(&hard_iface->bat_v.elp_interval) - BATADV_JITTER; + msecs += prandom_u32() % (2 * BATADV_JITTER); + + queue_delayed_work(batadv_event_workqueue, &hard_iface->bat_v.elp_wq, + msecs_to_jiffies(msecs)); +} + +/** + * batadv_v_elp_send_outstanding - ELP periodic broadcast sending + * @work: work queue item + * + * Sends a broadcast ELP message over the interface that this work item belongs + * to. + */ +static void batadv_v_elp_send_outstanding(struct work_struct *work) +{ + struct batadv_hard_iface *hard_iface; + struct batadv_hard_iface_bat_v *bat_v; + struct batadv_priv *bat_priv; + struct batadv_elp_packet *elp_packet; + uint32_t elp_interval; + struct sk_buff *skb; + + bat_v = container_of(work, struct batadv_hard_iface_bat_v, elp_wq.work); + hard_iface = container_of(bat_v, struct batadv_hard_iface, bat_v); + bat_priv = netdev_priv(hard_iface->soft_iface); + + if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_DEACTIVATING) + goto out; + + /* we are in the process of shutting this interface down */ + if ((hard_iface->if_status == BATADV_IF_NOT_IN_USE) || + (hard_iface->if_status == BATADV_IF_TO_BE_REMOVED)) + goto out; + + /* the interface was enabled but may not be ready yet */ + if (hard_iface->if_status != BATADV_IF_ACTIVE) + goto restart_timer; + + skb = skb_copy(hard_iface->bat_v.elp_skb, GFP_ATOMIC); + if (!skb) + goto out; + + elp_packet = (struct batadv_elp_packet *)skb->data; + elp_packet->seqno = htonl(atomic_read(&hard_iface->bat_v.elp_seqno)); + elp_packet->num_neighbors = 0; + elp_interval = atomic_read(&hard_iface->bat_v.elp_interval); + elp_packet->elp_interval = htonl(elp_interval); + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Sending ELP packet on interface %s, seqno %u\n", + hard_iface->net_dev->name, + atomic_read(&hard_iface->bat_v.elp_seqno)); + + batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); + + atomic_inc(&hard_iface->bat_v.elp_seqno); + +restart_timer: + batadv_v_elp_start_timer(hard_iface); +out: + return; +} + +/** + * batadv_v_elp_iface_enable - setup the ELP interface private resources + * @hard_iface: interface for which the data has to be prepared + * + * Returns 0 on success or a -ENOMEM in case of failure. + */ +int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface) +{ + struct batadv_elp_packet *elp_packet; + unsigned char *elp_buff; + uint32_t random_seqno; + size_t size; + int res = -ENOMEM; + + size = ETH_HLEN + NET_IP_ALIGN + BATADV_ELP_HLEN; + hard_iface->bat_v.elp_skb = dev_alloc_skb(size); + if (!hard_iface->bat_v.elp_skb) + goto out; + + skb_reserve(hard_iface->bat_v.elp_skb, ETH_HLEN + NET_IP_ALIGN); + elp_buff = skb_push(hard_iface->bat_v.elp_skb, BATADV_ELP_HLEN); + elp_packet = (struct batadv_elp_packet *)elp_buff; + memset(elp_packet, 0, BATADV_ELP_HLEN); + + elp_packet->packet_type = BATADV_ELP; + elp_packet->version = BATADV_COMPAT_VERSION; + elp_packet->ttl = 0; + + /* randomize initial seqno to avoid collision */ + get_random_bytes(&random_seqno, sizeof(random_seqno)); + atomic_set(&hard_iface->bat_v.elp_seqno, random_seqno); + atomic_set(&hard_iface->bat_v.elp_interval, 500); + + INIT_DELAYED_WORK(&hard_iface->bat_v.elp_wq, + batadv_v_elp_send_outstanding); + batadv_v_elp_start_timer(hard_iface); + res = 0; + +out: + return res; +} + +/** + * batadv_v_elp_iface_disable - release ELP interface private resources + * @hard_iface: interface for which the resources have to be released + */ +void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface) +{ + cancel_delayed_work_sync(&hard_iface->bat_v.elp_wq); + + dev_kfree_skb(hard_iface->bat_v.elp_skb); + hard_iface->bat_v.elp_skb = NULL; +} + +/** + * batadv_v_elp_primary_iface_set - change internal data to reflect the new + * primary interface + * @hard_iface: the new primary interface + */ +void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface) +{ + struct batadv_hard_iface *hard_iface_tmp; + struct batadv_elp_packet *elp_packet; + struct sk_buff *skb; + + /* update orig field of every elp iface belonging to this mesh */ + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface_tmp, &batadv_hardif_list, list) { + if (hard_iface->soft_iface != hard_iface_tmp->soft_iface) + continue; + + if (!hard_iface_tmp->bat_v.elp_skb) + continue; + + skb = hard_iface_tmp->bat_v.elp_skb; + elp_packet = (struct batadv_elp_packet *)skb->data; + memcpy(elp_packet->orig, + hard_iface->net_dev->dev_addr, ETH_ALEN); + } + rcu_read_unlock(); +} diff --git a/bat_v_elp.h b/bat_v_elp.h new file mode 100644 index 0000000..06d2cb1 --- /dev/null +++ b/bat_v_elp.h @@ -0,0 +1,30 @@ +/* Copyright (C) 2013-2014 B.A.T.M.A.N. contributors: + * + * Antonio Quartulli + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include "main.h" + +#ifndef _NET_BATMAN_ADV_BAT_V_ELP_H_ +#define _NET_BATMAN_ADV_BAT_V_ELP_H_ + +int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface); +void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface); +void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface); + +#endif /* _NET_BATMAN_ADV_BAT_V_ELP_H_ */ diff --git a/gen-compat-autoconf.sh b/gen-compat-autoconf.sh index 78573e4..001707f 100755 --- a/gen-compat-autoconf.sh +++ b/gen-compat-autoconf.sh @@ -40,6 +40,7 @@ gen_config 'CONFIG_BATMAN_ADV_DEBUG' ${CONFIG_BATMAN_ADV_DEBUG:="n"} >> "${TMP}" gen_config 'CONFIG_BATMAN_ADV_BLA' ${CONFIG_BATMAN_ADV_BLA:="y"} >> "${TMP}" gen_config 'CONFIG_BATMAN_ADV_DAT' ${CONFIG_BATMAN_ADV_DAT:="y"} >> "${TMP}" gen_config 'CONFIG_BATMAN_ADV_NC' ${CONFIG_BATMAN_ADV_NC:="n"} >> "${TMP}" +gen_config 'CONFIG_BATMAN_ADV_BATMAN_V' ${CONFIG_BATMAN_ADV_BATMAN_V:="n"} >> "${TMP}"

# only regenerate compat-autoconf.h when config was changed diff "${TMP}" "${TARGET}" > /dev/null 2>&1 || cp "${TMP}" "${TARGET}" diff --git a/main.c b/main.c index fbeaebd..b7d9996 100644 --- a/main.c +++ b/main.c @@ -63,6 +63,7 @@ static int __init batadv_init(void)

batadv_recv_handler_init();

+ batadv_v_init(); batadv_iv_init(); batadv_nc_init();

diff --git a/packet.h b/packet.h index 0a381d1..71b1aeb 100644 --- a/packet.h +++ b/packet.h @@ -37,6 +37,7 @@ enum batadv_packettype { BATADV_IV_OGM = 0x00, BATADV_BCAST = 0x01, BATADV_CODED = 0x02, + BATADV_ELP = 0x03, /* 0x40 - 0x7f: unicast */ #define BATADV_UNICAST_MIN 0x40 BATADV_UNICAST = 0x40, @@ -192,6 +193,30 @@ struct batadv_ogm_packet { #define BATADV_OGM_HLEN sizeof(struct batadv_ogm_packet)

/** + * struct batadv_elp_packet - elp (neighbor discovery) packet + * @packet_type: batman-adv packet type, part of the general header + * @version: batman-adv protocol version, part of the genereal header + * @ttl: time to live for this packet, part of the genereal header + * @num_neighbors: number of already discovered neighbors + * @seqno: sequence number + * @elp_interval: currently used ELP sending interval + * @orig: originator mac address + * @align: not used - useful for alignment purposes only + */ +struct batadv_elp_packet { + uint8_t packet_type; + uint8_t version; + uint8_t ttl; + uint8_t num_neighbors; + __be32 seqno; + __be32 elp_interval; + uint8_t orig[ETH_ALEN]; + uint8_t align[2]; +}; + +#define BATADV_ELP_HLEN sizeof(struct batadv_elp_packet) + +/** * batadv_icmp_header - common members among all the ICMP packets * @packet_type: batman-adv packet type, part of the general header * @version: batman-adv protocol version, part of the genereal header diff --git a/types.h b/types.h index 9f52517..518fa81 100644 --- a/types.h +++ b/types.h @@ -70,6 +70,20 @@ struct batadv_hard_iface_bat_iv { };

/** + * struct batadv_hard_iface_bat_v - per hard interface B.A.T.M.A.N. V data + * @elp_interval: time interval between two ELP transmissions + * @elp_seqno: current ELP sequence number + * @elp_skb: base skb containing the ELP message to send + * @elp_wq: workqueue used to schedule ELP transmissions + */ +struct batadv_hard_iface_bat_v { + atomic_t elp_interval; + atomic_t elp_seqno; + struct sk_buff *elp_skb; + struct delayed_work elp_wq; +}; + +/** * struct batadv_hard_iface - network device known to batman-adv * @list: list node for batadv_hardif_list * @if_num: identificator of the interface @@ -83,6 +97,7 @@ struct batadv_hard_iface_bat_iv { * @soft_iface: the batman-adv interface which uses this network interface * @rcu: struct used for freeing in an RCU-safe manner * @bat_iv: BATMAN IV specific per hard interface data + * @bat_v: BATMAN V specific per hard interface data * @cleanup_work: work queue callback item for hard interface deinit * @debug_dir: dentry for nc subdir in batman-adv directory in debugfs */ @@ -98,6 +113,9 @@ struct batadv_hard_iface { struct net_device *soft_iface; struct rcu_head rcu; struct batadv_hard_iface_bat_iv bat_iv; +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + struct batadv_hard_iface_bat_v bat_v; +#endif struct work_struct cleanup_work; struct dentry *debug_dir; };

From: Linus Luessing linus.luessing@web.de

Lists all neighbours detected by the Echo Locating Protocol (ELP) and their metric values.

Initially Developed by Linus during a 6 months trainee study period in Ascom (Switzerland) AG.

Signed-off-by: Linus Luessing linus.luessing@web.de Signed-off-by: Marek Lindner lindner_marek@yahoo.de Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v_elp.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bat_v_elp.h | 1 + debugfs.c | 17 +++++++++++++ 3 files changed, 98 insertions(+)

diff --git a/bat_v_elp.c b/bat_v_elp.c index ee4207d..9c40415 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -379,3 +379,83 @@ out: consume_skb(skb); return NET_RX_SUCCESS; } + +/** + * batadv_v_elp_seq_print_neigh - print a single ELP neighbour node + * @seq: neighbour table seq_file struct + * @hard_iface: interface the neighbour is connected to + * @neigh: the neighbour node to print + */ +static void batadv_v_elp_seq_print_neigh(struct seq_file *seq, + struct batadv_hard_iface *hard_iface, + struct batadv_elp_neigh_node *neigh) +{ + int last_secs, last_msecs; + uint32_t metric; + + last_secs = jiffies_to_msecs(jiffies - neigh->last_seen) / 1000; + last_msecs = jiffies_to_msecs(jiffies - neigh->last_seen) % 1000; + metric = ewma_read(&neigh->metric); + + seq_printf(seq, "%pM %4i.%03is (%9u.%1u) [%10s]\n", + neigh->addr, last_secs, last_msecs, metric / 10, + metric % 10, hard_iface->net_dev->name); +} + +/** + * batadv_v_elp_seq_print_text - print the neighbour table + * @seq: neighbour table seq_file struct + * @offset: not used + * + * Returns always 0. + */ +int batadv_v_elp_seq_print_text(struct seq_file *seq, void *offset) +{ + struct net_device *net_dev = (struct net_device *)seq->private; + struct batadv_priv *bat_priv = netdev_priv(net_dev); + struct batadv_hard_iface *hard_iface, *primary_if; + struct batadv_elp_neigh_node *neigh; + int batman_count = 0; + + primary_if = batadv_primary_if_get_selected(bat_priv); + + if (!primary_if) { + seq_printf(seq, + "BATMAN mesh %s disabled - please specify interfaces to enable it\n", + net_dev->name); + goto out; + } + + if (primary_if->if_status != BATADV_IF_ACTIVE) { + seq_printf(seq, + "BATMAN mesh %s disabled - primary interface not active\n", + net_dev->name); + goto out; + } + + seq_printf(seq, "[B.A.T.M.A.N. adv %s, MainIF/MAC: %s/%pM (%s)]\n", + BATADV_SOURCE_VERSION, primary_if->net_dev->name, + primary_if->net_dev->dev_addr, net_dev->name); + seq_printf(seq, " %-15s %s (%11s) [%10s]\n", "Neighbor", + "last-seen", "metric", "IF"); + + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { + if (hard_iface->soft_iface != net_dev) + continue; + + hlist_for_each_entry_rcu(neigh, &hard_iface->bat_v.neigh_list, list) { + batadv_v_elp_seq_print_neigh(seq, hard_iface, neigh); + batman_count++; + } + } + rcu_read_unlock(); + + if (batman_count == 0) + seq_printf(seq, "No batman nodes in range ...\n"); + +out: + if (primary_if) + batadv_hardif_free_ref(primary_if); + return 0; +} diff --git a/bat_v_elp.h b/bat_v_elp.h index 186ff4b..4f34ecb 100644 --- a/bat_v_elp.h +++ b/bat_v_elp.h @@ -32,5 +32,6 @@ void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface); void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface); int batadv_v_elp_packet_recv(struct sk_buff *skb, struct batadv_hard_iface *if_incoming); +int batadv_v_elp_seq_print_text(struct seq_file *seq, void *offset);

#endif /* _NET_BATMAN_ADV_BAT_V_ELP_H_ */ diff --git a/debugfs.c b/debugfs.c index b758881..23990cf 100644 --- a/debugfs.c +++ b/debugfs.c @@ -20,6 +20,7 @@ #include <linux/debugfs.h>

#include "debugfs.h" +#include "bat_v_elp.h" #include "translation-table.h" #include "originator.h" #include "hard-interface.h" @@ -242,6 +243,16 @@ static int batadv_algorithms_open(struct inode *inode, struct file *file) return single_open(file, batadv_algo_seq_print_text, NULL); }

+#ifdef CONFIG_BATMAN_ADV_BATMAN_V +int batadv_v_elp_seq_print_text(struct seq_file *seq, void *offset); + +static int neighbors_open(struct inode *inode, struct file *file) +{ + struct net_device *net_dev = (struct net_device *)inode->i_private; + return single_open(file, batadv_v_elp_seq_print_text, net_dev); +} +#endif + static int batadv_originators_open(struct inode *inode, struct file *file) { struct net_device *net_dev = (struct net_device *)inode->i_private; @@ -346,6 +357,9 @@ static struct batadv_debuginfo *batadv_general_debuginfos[] = { };

/* The following attributes are per soft interface */ +#ifdef CONFIG_BATMAN_ADV_BATMAN_V +static BATADV_DEBUGINFO(neighbors, S_IRUGO, neighbors_open); +#endif static BATADV_DEBUGINFO(originators, S_IRUGO, batadv_originators_open); static BATADV_DEBUGINFO(gateways, S_IRUGO, batadv_gateways_open); static BATADV_DEBUGINFO(transtable_global, S_IRUGO, @@ -365,6 +379,9 @@ static BATADV_DEBUGINFO(nc_nodes, S_IRUGO, batadv_nc_nodes_open); #endif

static struct batadv_debuginfo *batadv_mesh_debuginfos[] = { +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + &batadv_debuginfo_neighbors, +#endif &batadv_debuginfo_originators, &batadv_debuginfo_gateways, &batadv_debuginfo_transtable_global,

From: Antonio Quartulli antonio@open-mesh.com

This is the initial implementation of the new OGM protocol (version 2). It has been designed to work on top of the newly added ELP.

In the previous version the OGM protocol was used to both measure link qualities and flood the network with the metric information. In this version the protocol is in charge of the latter task only, leaving the former to ELP.

This means being able to decouple the interval used by the neighbor discovery from the OGM broadcasting, which revealed to be costly in dense networks and needed to be relaxed so leading to a less responsive routing protocol.

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- Makefile.kbuild | 1 + bat_algo.h | 11 +++ bat_v.c | 36 ++++++++- bat_v_elp.c | 11 ++- bat_v_ogm.c | 230 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bat_v_ogm.h | 32 ++++++++ main.c | 31 +++++++- main.h | 1 + packet.h | 25 ++++++ types.h | 15 ++++ 10 files changed, 385 insertions(+), 8 deletions(-) create mode 100644 bat_v_ogm.c create mode 100644 bat_v_ogm.h

diff --git a/Makefile.kbuild b/Makefile.kbuild index ae9a6ca..8073940 100644 --- a/Makefile.kbuild +++ b/Makefile.kbuild @@ -20,6 +20,7 @@ obj-$(CONFIG_BATMAN_ADV) += batman-adv.o batman-adv-y += bat_iv_ogm.o batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v.o batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v_elp.o +batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v_ogm.o batman-adv-y += bitarray.o batman-adv-$(CONFIG_BATMAN_ADV_BLA) += bridge_loop_avoidance.o batman-adv-y += debugfs.o diff --git a/bat_algo.h b/bat_algo.h index 7289336..14cf89f 100644 --- a/bat_algo.h +++ b/bat_algo.h @@ -23,6 +23,8 @@ int batadv_iv_init(void); #ifdef CONFIG_BATMAN_ADV_BATMAN_V

int batadv_v_init(void); +int batadv_v_mesh_init(struct batadv_priv *bat_priv); +void batadv_v_mesh_free(struct batadv_priv *bat_priv);

#else

@@ -31,6 +33,15 @@ static inline int batadv_v_init(void) return 0; }

+static inline int batadv_v_mesh_init(struct batadv_priv *bat_priv) +{ + return 0; +} + +static inline void batadv_v_mesh_free(struct batadv_priv *bat_priv) +{ +} + #endif /* CONFIG_BATMAN_ADV_BATMAN_V */

#endif /* _NET_BATMAN_ADV_BAT_ALGO_H_ */ diff --git a/bat_v.c b/bat_v.c index bed5e00..b4214c5 100644 --- a/bat_v.c +++ b/bat_v.c @@ -20,10 +20,21 @@ #include "main.h" #include "bat_algo.h" #include "bat_v_elp.h" +#include "bat_v_ogm.h"

static int batadv_v_iface_enable(struct batadv_hard_iface *hard_iface) { - return batadv_v_elp_iface_enable(hard_iface); + int ret; + + ret = batadv_v_elp_iface_enable(hard_iface); + if (ret < 0) + return ret; + + ret = batadv_v_ogm_iface_enable(hard_iface); + if (ret < 0) + batadv_v_elp_iface_disable(hard_iface); + + return ret; }

static void batadv_v_iface_disable(struct batadv_hard_iface *hard_iface) @@ -38,6 +49,7 @@ static void batadv_v_iface_update_mac(struct batadv_hard_iface *hard_iface) static void batadv_v_primary_iface_set(struct batadv_hard_iface *hard_iface) { batadv_v_elp_primary_iface_set(hard_iface); + batadv_v_ogm_primary_iface_set(hard_iface); }

static void batadv_v_ogm_schedule(struct batadv_hard_iface *hard_iface) @@ -58,6 +70,15 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = { .bat_ogm_schedule = batadv_v_ogm_schedule, };

+int batadv_v_mesh_init(struct batadv_priv *bat_priv) +{ + return batadv_v_ogm_init(bat_priv); +} + +void batadv_v_mesh_free(struct batadv_priv *bat_priv) +{ + batadv_v_ogm_free(bat_priv); +}

int __init batadv_v_init(void) { @@ -67,15 +88,24 @@ int __init batadv_v_init(void) ret = batadv_recv_handler_register(BATADV_ELP, batadv_v_elp_packet_recv); if (ret < 0) + return ret; + + ret = batadv_recv_handler_register(BATADV_OGM2, + batadv_v_ogm_packet_recv); + if (ret < 0) goto elp_unregister;

ret = batadv_algo_register(&batadv_batman_v); + if (ret < 0) + goto ogm_unregister;

return ret;

+ogm_unregister: + batadv_recv_handler_unregister(BATADV_OGM2); + elp_unregister: - if (ret < 0) - batadv_recv_handler_unregister(BATADV_ELP); + batadv_recv_handler_unregister(BATADV_ELP);

return ret; } diff --git a/bat_v_elp.c b/bat_v_elp.c index 9c40415..1c23951 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -25,6 +25,7 @@ #include "bat_v_elp.h" #include "originator.h" #include "routing.h" +#include "translation-table.h"

/** * batadv_v_elp_start_timer - restart timer for ELP periodic work @@ -276,11 +277,15 @@ void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface) */ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface) { + struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); struct batadv_hard_iface *hard_iface_tmp; struct batadv_elp_packet *elp_packet; + struct batadv_ogm2_packet *ogm2; struct sk_buff *skb;

- /* update orig field of every elp iface belonging to this mesh */ + /* update orig field of every elp and ogm iface belonging to this + * mesh + */ rcu_read_lock(); list_for_each_entry_rcu(hard_iface_tmp, &batadv_hardif_list, list) { if (hard_iface->soft_iface != hard_iface_tmp->soft_iface) @@ -293,6 +298,9 @@ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface) elp_packet = (struct batadv_elp_packet *)skb->data; memcpy(elp_packet->orig, hard_iface->net_dev->dev_addr, ETH_ALEN); + + ogm2 = (struct batadv_ogm2_packet *)bat_priv->bat_v.ogm_buff; + memcpy(ogm2->orig, hard_iface->net_dev->dev_addr, ETH_ALEN); } rcu_read_unlock(); } @@ -311,6 +319,7 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv, uint8_t *neigh_addr, struct batadv_hard_iface *if_incoming, struct batadv_elp_packet *elp_packet) + { struct batadv_elp_neigh_node *neigh;

diff --git a/bat_v_ogm.c b/bat_v_ogm.c new file mode 100644 index 0000000..f66dc02 --- /dev/null +++ b/bat_v_ogm.c @@ -0,0 +1,230 @@ +/* + * Copyright (C) 2013 B.A.T.M.A.N. contributors: + * + * Antonio Quartulli + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#include "main.h" + +#include "bat_v_ogm.h" +#include "hard-interface.h" +#include "originator.h" +#include "routing.h" +#include "send.h" +#include "translation-table.h" + +static void batadv_v_ogm_start_timer(struct batadv_priv *bat_priv) +{ + unsigned long msecs; + /* this function may be invoked in different contexts (ogm rescheduling + * or hard_iface activation), but the work timer should not be reset + */ + if (delayed_work_pending(&bat_priv->bat_v.ogm_wq)) + return; + + msecs = atomic_read(&bat_priv->orig_interval) - BATADV_JITTER; + msecs += prandom_u32() % (2 * BATADV_JITTER); + queue_delayed_work(batadv_event_workqueue, &bat_priv->bat_v.ogm_wq, + msecs_to_jiffies(msecs)); +} + +/* send a batman ogm to a given interface */ +static void batadv_v_ogm_send_to_if(struct sk_buff *skb, + struct batadv_hard_iface *hard_iface) +{ + struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); + struct sk_buff *tmp_skb; + + if (hard_iface->if_status != BATADV_IF_ACTIVE) + return; + + tmp_skb = skb_clone(skb, GFP_ATOMIC); + if (!tmp_skb) + return; + + batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_TX); + batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES, + tmp_skb->len + ETH_HLEN); + + batadv_send_skb_packet(tmp_skb, hard_iface, batadv_broadcast_addr); +} + +static void batadv_v_ogm_send(struct work_struct *work) +{ + struct batadv_hard_iface *hard_iface; + struct batadv_priv_bat_v *bat_v; + struct batadv_priv *bat_priv; + struct batadv_ogm2_packet *ogm2; + struct sk_buff *skb; + unsigned char *ogm_buff, *pkt_buff; + int ogm_buff_len; + uint16_t tvlv_len = 0; + + bat_v = container_of(work, struct batadv_priv_bat_v, ogm_wq.work); + bat_priv = container_of(bat_v, struct batadv_priv, bat_v); + + if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_DEACTIVATING) + goto out; + + ogm_buff = bat_priv->bat_v.ogm_buff; + ogm_buff_len = bat_priv->bat_v.ogm_buff_len; + /* tt changes have to be committed before the tvlv data is + * appended as it may alter the tt tvlv container + */ + batadv_tt_local_commit_changes(bat_priv); + tvlv_len = batadv_tvlv_container_ogm_append(bat_priv, &ogm_buff, + &ogm_buff_len, + BATADV_OGM2_HLEN); + + bat_priv->bat_v.ogm_buff = ogm_buff; + bat_priv->bat_v.ogm_buff_len = ogm_buff_len; + + skb = netdev_alloc_skb_ip_align(NULL, ETH_HLEN + ogm_buff_len); + if (!skb) + goto out; + + skb_reserve(skb, ETH_HLEN); + pkt_buff = skb_put(skb, ogm_buff_len); + memcpy(pkt_buff, ogm_buff, ogm_buff_len); + + ogm2 = (struct batadv_ogm2_packet *)skb->data; + ogm2->seqno = htonl(atomic_read(&bat_priv->bat_v.ogm_seqno)); + atomic_inc(&bat_priv->bat_v.ogm_seqno); + ogm2->tvlv_len = htons(tvlv_len); + + /* broadcast on every interface */ + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { + if (hard_iface->soft_iface != bat_priv->soft_iface) + continue; + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Sending own OGM2 packet (originator %pM, seqno %u, metric %u, TTL %d) on interface %s [%pM]\n", + ogm2->orig, ntohl(ogm2->seqno), ntohl(ogm2->metric), + ogm2->ttl, hard_iface->net_dev->name, + hard_iface->net_dev->dev_addr); + + batadv_v_ogm_send_to_if(skb, hard_iface); + } + rcu_read_unlock(); + + consume_skb(skb); + + batadv_v_ogm_start_timer(bat_priv); +out: + return; +} + +int batadv_v_ogm_iface_enable(struct batadv_hard_iface *hard_iface) +{ + struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); + + batadv_v_ogm_start_timer(bat_priv); + + return 0; +} + +void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *hard_iface) +{ + struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); + struct batadv_hard_iface *hard_iface_tmp; + struct batadv_ogm2_packet *ogm2; + + /* update orig field of every elp and ogm iface belonging to this + * mesh + */ + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface_tmp, &batadv_hardif_list, list) { + if (hard_iface->soft_iface != hard_iface_tmp->soft_iface) + continue; + + if (!hard_iface_tmp->bat_v.elp_skb) + continue; + + ogm2 = (struct batadv_ogm2_packet *)bat_priv->bat_v.ogm_buff; + memcpy(ogm2->orig, hard_iface->net_dev->dev_addr, ETH_ALEN); + } + rcu_read_unlock(); +} + +int batadv_v_ogm_packet_recv(struct sk_buff *skb, + struct batadv_hard_iface *if_incoming) +{ struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); + struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb); + struct batadv_ogm2_packet *ogm2; + + /* did we receive a OGM2 packet on an interface that does not have + * B.A.T.M.A.N. V enabled ? + */ + if (strcmp(bat_priv->bat_algo_ops->name, "BATMAN_V") != 0) + return NET_RX_DROP; + + if (!batadv_check_management_packet(skb, if_incoming, BATADV_OGM2_HLEN)) + return NET_RX_DROP; + + if (batadv_is_my_mac(bat_priv, ethhdr->h_source)) + return NET_RX_DROP; + + ogm2 = (struct batadv_ogm2_packet *)skb->data; + + if (batadv_is_my_mac(bat_priv, ogm2->orig)) + return NET_RX_DROP; + + batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_RX); + batadv_add_counter(bat_priv, BATADV_CNT_MGMT_RX_BYTES, + skb->len + ETH_HLEN); + + consume_skb(skb); + return NET_RX_SUCCESS; +} + +int batadv_v_ogm_init(struct batadv_priv *bat_priv) +{ + struct batadv_ogm2_packet *ogm2; + unsigned char *ogm_buff; + uint32_t random_seqno; + + bat_priv->bat_v.ogm_buff_len = BATADV_OGM2_HLEN; + ogm_buff = kmalloc(bat_priv->bat_v.ogm_buff_len, GFP_ATOMIC); + if (!ogm_buff) + return -ENOMEM; + + bat_priv->bat_v.ogm_buff = ogm_buff; + ogm2 = (struct batadv_ogm2_packet *)ogm_buff; + ogm2->packet_type = BATADV_OGM2; + ogm2->version = BATADV_COMPAT_VERSION; + ogm2->ttl = BATADV_TTL; + ogm2->flags = BATADV_NO_FLAGS; + ogm2->metric = htonl(BATADV_MAX_METRIC); + + /* randomize initial seqno to avoid collision */ + get_random_bytes(&random_seqno, sizeof(random_seqno)); + atomic_set(&bat_priv->bat_v.ogm_seqno, random_seqno); + INIT_DELAYED_WORK(&bat_priv->bat_v.ogm_wq, batadv_v_ogm_send); + + return 0; +} + +void batadv_v_ogm_free(struct batadv_priv *bat_priv) +{ + cancel_delayed_work_sync(&bat_priv->bat_v.ogm_wq); + + kfree(bat_priv->bat_v.ogm_buff); + bat_priv->bat_v.ogm_buff = NULL; + bat_priv->bat_v.ogm_buff_len = 0; +} diff --git a/bat_v_ogm.h b/bat_v_ogm.h new file mode 100644 index 0000000..7f7341e --- /dev/null +++ b/bat_v_ogm.h @@ -0,0 +1,32 @@ +/* + * Copyright (C) 2013 B.A.T.M.A.N. contributors: + * + * Antonio Quartulli + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#ifndef _BATAMAN_ADV_BATADV_V_OGM_H_ +#define _BATAMAN_ADV_BATADV_V_OGM_H_ + +int batadv_v_ogm_init(struct batadv_priv *bat_priv); +void batadv_v_ogm_free(struct batadv_priv *bat_priv); +int batadv_v_ogm_iface_enable(struct batadv_hard_iface *hard_iface); +void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *hard_iface); +int batadv_v_ogm_packet_recv(struct sk_buff *skb, + struct batadv_hard_iface *if_incoming); + +#endif /* _BATAMAN_ADV_BATADV_V_OGM_H_ */ diff --git a/main.c b/main.c index b7d9996..424fa82 100644 --- a/main.c +++ b/main.c @@ -35,6 +35,7 @@ #include "bridge_loop_avoidance.h" #include "distributed-arp-table.h" #include "gateway_common.h" +#include "hard-interface.h" #include "hash.h" #include "bat_algo.h" #include "network-coding.h" @@ -125,6 +126,10 @@ int batadv_mesh_init(struct net_device *soft_iface) INIT_HLIST_HEAD(&bat_priv->tvlv.handler_list); INIT_HLIST_HEAD(&bat_priv->softif_vlan_list);

+ ret = batadv_v_mesh_init(bat_priv); + if (ret < 0) + goto err; + ret = batadv_originator_init(bat_priv); if (ret < 0) goto err; @@ -165,6 +170,8 @@ void batadv_mesh_free(struct net_device *soft_iface)

batadv_purge_outstanding_packets(bat_priv, NULL);

+ batadv_v_mesh_free(bat_priv); + batadv_gw_node_purge(bat_priv); batadv_nc_mesh_free(bat_priv); batadv_dat_free(bat_priv); @@ -835,21 +842,32 @@ uint16_t batadv_tvlv_container_ogm_append(struct batadv_priv *bat_priv, { struct batadv_tvlv_container *tvlv; struct batadv_tvlv_hdr *tvlv_hdr; - uint16_t tvlv_value_len; + uint16_t tvlv_value_len = 0; void *tvlv_value; bool ret; + struct batadv_hard_iface *primary_if; + + primary_if = batadv_primary_if_get_selected(bat_priv); + if (!primary_if) + goto end;

spin_lock_bh(&bat_priv->tvlv.container_list_lock); tvlv_value_len = batadv_tvlv_container_list_size(bat_priv);

+ if (packet_min_len + tvlv_value_len > primary_if->net_dev->mtu) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "OGM size too big to fit the primary_if mtu\n"); + goto unlock; + } + ret = batadv_tvlv_realloc_packet_buff(packet_buff, packet_buff_len, packet_min_len, tvlv_value_len);

if (!ret) - goto end; + goto unlock;

if (!tvlv_value_len) - goto end; + goto unlock;

tvlv_value = (*packet_buff) + packet_min_len;

@@ -863,8 +881,13 @@ uint16_t batadv_tvlv_container_ogm_append(struct batadv_priv *bat_priv, tvlv_value = (uint8_t *)tvlv_value + ntohs(tvlv->tvlv_hdr.len); }

-end: +unlock: spin_unlock_bh(&bat_priv->tvlv.container_list_lock); + +end: + if (primary_if) + batadv_hardif_free_ref(primary_if); + return tvlv_value_len; }

diff --git a/main.h b/main.h index 4ab3216..4badd01 100644 --- a/main.h +++ b/main.h @@ -30,6 +30,7 @@ /* B.A.T.M.A.N. parameters */

#define BATADV_TQ_MAX_VALUE 255 +#define BATADV_MAX_METRIC 0xFFFFFFFF #define BATADV_JITTER 20

/* Time To Live of broadcast messages */ diff --git a/packet.h b/packet.h index 71b1aeb..a985802 100644 --- a/packet.h +++ b/packet.h @@ -38,6 +38,7 @@ enum batadv_packettype { BATADV_BCAST = 0x01, BATADV_CODED = 0x02, BATADV_ELP = 0x03, + BATADV_OGM2 = 0x0d, /* 0x40 - 0x7f: unicast */ #define BATADV_UNICAST_MIN 0x40 BATADV_UNICAST = 0x40, @@ -193,6 +194,30 @@ struct batadv_ogm_packet { #define BATADV_OGM_HLEN sizeof(struct batadv_ogm_packet)

/** + * struct batadv_ogm2_packet - ogm2 (routing protocol) packet + * @packet_type: batman-adv packet type, part of the general header + * @version: batman-adv protocol version, part of the general header + * @ttl: time to live for this packet, part of the general header + * @flags: + * @seqno: sequence number + * @orig: originator mac address + * @tvlv_len: length of the appended tvlv buffer (in bytes) + * @metric: the currently flooded metric value + */ +struct batadv_ogm2_packet { + uint8_t packet_type; + uint8_t version; + uint8_t ttl; + uint8_t flags; + __be32 seqno; + uint8_t orig[ETH_ALEN]; + __be16 tvlv_len; + __be32 metric; +}; + +#define BATADV_OGM2_HLEN sizeof(struct batadv_ogm2_packet) + +/** * struct batadv_elp_packet - elp (neighbor discovery) packet * @packet_type: batman-adv packet type, part of the general header * @version: batman-adv protocol version, part of the genereal header diff --git a/types.h b/types.h index be230b6..e9149d1 100644 --- a/types.h +++ b/types.h @@ -728,6 +728,18 @@ struct batadv_softif_vlan { };

/** + * struct batadv_priv_bat_v - + * @ogm_buff: + * @ogm_buff_len: + */ +struct batadv_priv_bat_v { + unsigned char *ogm_buff; + int ogm_buff_len; + struct delayed_work ogm_wq; + atomic_t ogm_seqno; +}; + +/** * struct batadv_priv - per mesh interface data * @mesh_state: current status of the mesh (inactive/active/deactivating) * @soft_iface: net device which holds this struct as private data @@ -834,6 +846,9 @@ struct batadv_priv { atomic_t network_coding; struct batadv_priv_nc nc; #endif /* CONFIG_BATMAN_ADV_NC */ +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + struct batadv_priv_bat_v bat_v; +#endif };

/**

From: Antonio Quartulli antonio@open-mesh.com

If a neighbor is not forwarding OGMs since OGM_SEQ_RANGE sequence numbers then it can be considered obsolete and removed from the potential routers list. This may lead to a route switch.

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v_ogm.c | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- main.h | 3 ++ originator.c | 63 +++++++++++++++++++++++------------------ originator.h | 2 ++ types.h | 2 ++ 5 files changed, 131 insertions(+), 31 deletions(-)

diff --git a/bat_v_ogm.c b/bat_v_ogm.c index 4981d7c..5876164 100644 --- a/bat_v_ogm.c +++ b/bat_v_ogm.c @@ -79,8 +79,6 @@ batadv_v_ogm_neigh_new(struct batadv_priv *bat_priv, return NULL; }

- neigh_node->bat_v.elp_neigh = elp_neigh; - spin_lock_bh(&orig_node->neigh_list_lock); tmp_neigh_node = batadv_neigh_node_get(orig_node, hard_iface, addr); if (!tmp_neigh_node) { @@ -98,6 +96,8 @@ batadv_v_ogm_neigh_new(struct batadv_priv *bat_priv, "Creating new neighbor %pM for orig_node %pM on interface %s\n", addr, orig_node->orig, hard_iface->net_dev->name);

+ neigh_node->bat_v.elp_neigh = elp_neigh; + return neigh_node; }

@@ -235,6 +235,86 @@ void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *hard_iface) rcu_read_unlock(); }

+static bool batadv_ogm_deselect_router(struct batadv_priv *bat_priv, + struct batadv_orig_node *orig_node, + struct batadv_neigh_node *neigh) +{ + struct batadv_hard_iface *if_outgoing; + struct batadv_neigh_node *router; + bool removed = false; + + router = batadv_orig_router_get(orig_node, BATADV_IF_DEFAULT); + if (router == neigh) + batadv_update_route(bat_priv, orig_node, BATADV_IF_DEFAULT, + NULL); + if (router) + batadv_neigh_node_free_ref(router); + + rcu_read_lock(); + list_for_each_entry_rcu(if_outgoing, &batadv_hardif_list, list) { + if (if_outgoing->if_status != BATADV_IF_ACTIVE) + continue; + + if (if_outgoing->soft_iface != bat_priv->soft_iface) + continue; + + router = batadv_orig_router_get(orig_node, if_outgoing); + /* if this is the current router, unset it */ + if (router == neigh) { + batadv_update_route(bat_priv, orig_node, if_outgoing, + NULL); + removed = true; + } + if (router) + batadv_neigh_node_free_ref(router); + } + rcu_read_unlock(); + + return removed; +} + +/** + * batadv_v_ogm_purge_neighs - purge obsolete potential routers + * @bat_priv: + * @orig_node: + * @seqno: + * + * Purge routers from which this node did not receive at least + * BATADV_OGM_SEQ_RANGE OGMs + */ +static void batadv_v_ogm_purge_neighs(struct batadv_priv *bat_priv, + struct batadv_orig_node *orig_node, + uint32_t seqno) +{ + struct batadv_neigh_node *neigh; + struct hlist_node *node_tmp; + int32_t diff; + + rcu_read_lock(); + spin_lock_bh(&orig_node->neigh_list_lock); + hlist_for_each_entry_safe(neigh, node_tmp, &orig_node->neigh_list, + list) { + diff = seqno - neigh->bat_v.last_recv_seqno; + if (diff < BATADV_OGM_SEQ_RANGE) + continue; + + hlist_del_rcu(&neigh->list); + batadv_neigh_node_free_ref(neigh); + } + spin_unlock_bh(&orig_node->neigh_list_lock); + + /* check if this neighbour is a router for any outgoing + * interface and possibly deselect it + */ + if (batadv_ogm_deselect_router(bat_priv, orig_node, neigh)) + goto out; + + batadv_router_selection(bat_priv, orig_node); +out: + rcu_read_unlock(); + return; +} + static void batadv_v_ogm_orig_update(struct batadv_priv *bat_priv, struct batadv_orig_node *orig_node, @@ -262,7 +342,7 @@ batadv_v_ogm_orig_update(struct batadv_priv *bat_priv, batadv_orig_ifinfo_free_ref(orig_ifinfo);

/* if this neighbor already is our next hop there is nothing - * to change + * to change. The router may have been changed by the purge routine */ router = batadv_orig_router_get(orig_node, if_outgoing); if (router == neigh_node) @@ -547,6 +627,7 @@ int batadv_v_ogm_packet_recv(struct sk_buff *skb,

/* update the neigh_node information */ neigh_node->last_seen = jiffies; + neigh_node->bat_v.last_recv_seqno = ntohl(ogm2->seqno);

/* update the received metric to match the node topology: if this node * is the first hop traversed by the OGM, then the metric is substituted @@ -579,6 +660,11 @@ int batadv_v_ogm_packet_recv(struct sk_buff *skb, } rcu_read_unlock();

+ /* purge potential neighs not forwarding OGMs anymore. + * This may lead to a router change + */ + batadv_v_ogm_purge_neighs(bat_priv, orig_node, ntohl(ogm2->seqno)); + ret = NET_RX_SUCCESS; consume_skb(skb);

diff --git a/main.h b/main.h index 4badd01..47fb9ed 100644 --- a/main.h +++ b/main.h @@ -62,6 +62,9 @@ /* number of OGMs sent with the last tt diff */ #define BATADV_TT_OGM_APPEND_MAX 3

+/* number of missing OGMs to wait before considering a router unusable */ +#define BATADV_OGM_SEQ_RANGE 5 + /* Time in which a client can roam at most ROAMING_MAX_COUNT times in * milliseconds */ diff --git a/originator.c b/originator.c index 9f2da37..447f417 100644 --- a/originator.c +++ b/originator.c @@ -837,6 +837,40 @@ batadv_find_best_neighbor(struct batadv_priv *bat_priv, return best; }

+void batadv_router_selection(struct batadv_priv *bat_priv, + struct batadv_orig_node *orig_node) +{ + struct batadv_neigh_node *best_neigh_node; + struct batadv_hard_iface *hard_iface; + + /* First for the default routing table ... */ + best_neigh_node = batadv_find_best_neighbor(bat_priv, orig_node, + BATADV_IF_DEFAULT); + batadv_update_route(bat_priv, orig_node, BATADV_IF_DEFAULT, + best_neigh_node); + if (best_neigh_node) + batadv_neigh_node_free_ref(best_neigh_node); + + /* ... then for all other outgoing interfaces. */ + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { + if (hard_iface->if_status != BATADV_IF_ACTIVE) + continue; + + if (hard_iface->soft_iface != bat_priv->soft_iface) + continue; + + best_neigh_node = batadv_find_best_neighbor(bat_priv, + orig_node, + hard_iface); + batadv_update_route(bat_priv, orig_node, hard_iface, + best_neigh_node); + if (best_neigh_node) + batadv_neigh_node_free_ref(best_neigh_node); + } + rcu_read_unlock(); +} + /** * batadv_purge_orig_node - purges obsolete information from an orig_node * @bat_priv: the bat priv with all the soft interface information @@ -850,8 +884,6 @@ batadv_find_best_neighbor(struct batadv_priv *bat_priv, static bool batadv_purge_orig_node(struct batadv_priv *bat_priv, struct batadv_orig_node *orig_node) { - struct batadv_neigh_node *best_neigh_node; - struct batadv_hard_iface *hard_iface; bool changed;

if (batadv_has_timed_out(orig_node->last_seen, @@ -868,32 +900,7 @@ static bool batadv_purge_orig_node(struct batadv_priv *bat_priv, if (!changed) return false;

- /* first for NULL ... */ - best_neigh_node = batadv_find_best_neighbor(bat_priv, orig_node, - BATADV_IF_DEFAULT); - batadv_update_route(bat_priv, orig_node, BATADV_IF_DEFAULT, - best_neigh_node); - if (best_neigh_node) - batadv_neigh_node_free_ref(best_neigh_node); - - /* ... then for all other interfaces. */ - rcu_read_lock(); - list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { - if (hard_iface->if_status != BATADV_IF_ACTIVE) - continue; - - if (hard_iface->soft_iface != bat_priv->soft_iface) - continue; - - best_neigh_node = batadv_find_best_neighbor(bat_priv, - orig_node, - hard_iface); - batadv_update_route(bat_priv, orig_node, hard_iface, - best_neigh_node); - if (best_neigh_node) - batadv_neigh_node_free_ref(best_neigh_node); - } - rcu_read_unlock(); + batadv_router_selection(bat_priv, orig_node);

return false; } diff --git a/originator.h b/originator.h index db3a9ed..62e8e68 100644 --- a/originator.h +++ b/originator.h @@ -55,6 +55,8 @@ struct batadv_orig_ifinfo * batadv_orig_ifinfo_new(struct batadv_orig_node *orig_node, struct batadv_hard_iface *if_outgoing); void batadv_orig_ifinfo_free_ref(struct batadv_orig_ifinfo *orig_ifinfo); +void batadv_router_selection(struct batadv_priv *bat_priv, + struct batadv_orig_node *orig_node);

int batadv_orig_seq_print_text(struct seq_file *seq, void *offset); int batadv_orig_hardif_seq_print_text(struct seq_file *seq, void *offset); diff --git a/types.h b/types.h index e9149d1..28f2b85 100644 --- a/types.h +++ b/types.h @@ -358,9 +358,11 @@ struct batadv_elp_neigh_node { /** * batadv_neigh_node_bat_v - B.A.T.M.A.N. V private neighbor information * @elp_neigh: ELP private neighbour data + * @last_recv_seqno: last OGM seqno received through this neighbour */ struct batadv_neigh_node_bat_v { struct batadv_elp_neigh_node *elp_neigh; + uint32_t last_recv_seqno; };

/**

From: Antonio Quartulli antonio@open-mesh.com

This attribute is exported to the user which can manually select its value. It is the throughput value to be used by default when batman-adv is trying to compute the link throughput towards a neighbour using this interface.

If the value is set to 0 then batman-adv will try to detect the throughput by itself.

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v.c | 3 +++ sysfs.c | 3 +++ types.h | 2 ++ 3 files changed, 8 insertions(+)

diff --git a/bat_v.c b/bat_v.c index b4214c5..d5457b3 100644 --- a/bat_v.c +++ b/bat_v.c @@ -34,6 +34,9 @@ static int batadv_v_iface_enable(struct batadv_hard_iface *hard_iface) if (ret < 0) batadv_v_elp_iface_disable(hard_iface);

+ /* disable user customised throughput by default */ + atomic_set(&hard_iface->bat_v.user_throughput, 0); + return ret; }

diff --git a/sysfs.c b/sysfs.c index 9139319..8bbbdfa 100644 --- a/sysfs.c +++ b/sysfs.c @@ -889,6 +889,8 @@ static BATADV_ATTR(iface_status, S_IRUGO, batadv_show_iface_status, NULL); #ifdef CONFIG_BATMAN_ADV_BATMAN_V BATADV_ATTR_HIF_UINT(elp_interval, bat_v.elp_interval, S_IRUGO | S_IWUSR, 2 * BATADV_JITTER, INT_MAX, NULL); +BATADV_ATTR_HIF_UINT(throughput, bat_v.user_throughput, S_IRUGO | S_IWUSR, + 0, UINT_MAX, NULL); #endif

static struct batadv_attribute *batadv_batman_attrs[] = { @@ -896,6 +898,7 @@ static struct batadv_attribute *batadv_batman_attrs[] = { &batadv_attr_iface_status, #ifdef CONFIG_BATMAN_ADV_BATMAN_V &batadv_attr_elp_interval, + &batadv_attr_throughput, #endif NULL, }; diff --git a/types.h b/types.h index 28f2b85..64316b9 100644 --- a/types.h +++ b/types.h @@ -78,6 +78,7 @@ struct batadv_hard_iface_bat_iv { * @num_neighbours: number of neighbours in the neigh_list * @elp_skb: base skb containing the ELP message to send * @elp_wq: workqueue used to schedule ELP transmissions + * @user_throughput: user specified throughput */ struct batadv_hard_iface_bat_v { atomic_t elp_interval; @@ -87,6 +88,7 @@ struct batadv_hard_iface_bat_v { atomic_t num_neighbors; struct sk_buff *elp_skb; struct delayed_work elp_wq; + atomic_t user_throughput; };

/**

From: Antonio Quartulli antonio@open-mesh.com

when batman-adv is asked to estimate/compute the throughput of an interface, but it fails for whatever reason, then the value in this attribute is used

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v.c | 3 +++ main.h | 7 +++++++ sysfs.c | 7 +++++++ types.h | 1 + 4 files changed, 18 insertions(+)

diff --git a/bat_v.c b/bat_v.c index d5457b3..3aa42ec 100644 --- a/bat_v.c +++ b/bat_v.c @@ -75,6 +75,9 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = {

int batadv_v_mesh_init(struct batadv_priv *bat_priv) { + atomic_set(&bat_priv->bat_v.base_throughput, + BATADV_DEFAULT_BASE_THROUGHPUT); + return batadv_v_ogm_init(bat_priv); }

diff --git a/main.h b/main.h index 47fb9ed..5699c9f 100644 --- a/main.h +++ b/main.h @@ -33,6 +33,13 @@ #define BATADV_MAX_METRIC 0xFFFFFFFF #define BATADV_JITTER 20

+/** + * BATADV_DEFAULT_BASE_THROUGHPUT - default value used as throughput for + * hard_ifaces for which it is not possible to measure/estimate the real one. + * Value is expressed in Mbps/10 + */ +#define BATADV_DEFAULT_BASE_THROUGHPUT 10 + /* Time To Live of broadcast messages */ #define BATADV_TTL 50

diff --git a/sysfs.c b/sysfs.c index 8bbbdfa..a670eeb 100644 --- a/sysfs.c +++ b/sysfs.c @@ -606,6 +606,10 @@ BATADV_ATTR_SIF_BOOL(network_coding, S_IRUGO | S_IWUSR, #endif static BATADV_ATTR(isolation_mark, S_IRUGO | S_IWUSR, batadv_show_isolation_mark, batadv_store_isolation_mark); +#ifdef CONFIG_BATMAN_ADV_BATMAN_V +BATADV_ATTR_SIF_UINT2(base_throughput, bat_v.base_throughput, S_IRUGO | S_IWUSR, + 1, UINT_MAX, NULL); +#endif

static struct batadv_attribute *batadv_mesh_attrs[] = { &batadv_attr_aggregated_ogms, @@ -630,6 +634,9 @@ static struct batadv_attribute *batadv_mesh_attrs[] = { &batadv_attr_network_coding, #endif &batadv_attr_isolation_mark, +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + &batadv_attr_base_throughput, +#endif NULL, };

diff --git a/types.h b/types.h index 64316b9..22d621e 100644 --- a/types.h +++ b/types.h @@ -741,6 +741,7 @@ struct batadv_priv_bat_v { int ogm_buff_len; struct delayed_work ogm_wq; atomic_t ogm_seqno; + atomic_t base_throughput; };

/**

From: Antonio Quartulli antonio@open-mesh.com

This timestamp registers the last time a unicast packet was sent to a given neighbour

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_iv_ogm.c | 2 +- bat_v_elp.c | 2 +- bat_v_ogm.c | 2 +- distributed-arp-table.c | 4 +--- fragmentation.c | 8 +++----- icmp_socket.c | 2 +- network-coding.c | 20 +++++++++----------- send.c | 46 +++++++++++++++++++++++++++++++++++++++------- send.h | 10 +++++++--- types.h | 2 ++ 10 files changed, 65 insertions(+), 33 deletions(-)

diff --git a/bat_iv_ogm.c b/bat_iv_ogm.c index f92253a..e2069c9 100644 --- a/bat_iv_ogm.c +++ b/bat_iv_ogm.c @@ -469,7 +469,7 @@ static void batadv_iv_ogm_send_to_if(struct batadv_forw_packet *forw_packet, batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_TX); batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES, skb->len + ETH_HLEN); - batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); + batadv_send_broadcast_skb(skb, hard_iface); } }

diff --git a/bat_v_elp.c b/bat_v_elp.c index f9a6bfe..4185d8c 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -200,7 +200,7 @@ static void batadv_v_elp_send_outstanding(struct work_struct *work) hard_iface->net_dev->name, atomic_read(&hard_iface->bat_v.elp_seqno));

- batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); + batadv_send_broadcast_skb(skb, hard_iface);

atomic_inc(&hard_iface->bat_v.elp_seqno);

diff --git a/bat_v_ogm.c b/bat_v_ogm.c index 5876164..fa3d1a1 100644 --- a/bat_v_ogm.c +++ b/bat_v_ogm.c @@ -129,7 +129,7 @@ static void batadv_v_ogm_send_to_if(struct sk_buff *skb, batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES, skb->len + ETH_HLEN);

- batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); + batadv_send_broadcast_skb(skb, hard_iface); }

static void batadv_v_ogm_send(struct work_struct *work) diff --git a/distributed-arp-table.c b/distributed-arp-table.c index 78803b8..bc37033 100644 --- a/distributed-arp-table.c +++ b/distributed-arp-table.c @@ -602,9 +602,7 @@ static bool batadv_dat_send_data(struct batadv_priv *bat_priv, goto free_neigh; }

- send_status = batadv_send_skb_packet(tmp_skb, - neigh_node->if_incoming, - neigh_node->addr); + send_status = batadv_send_unicast_skb(tmp_skb, neigh_node); if (send_status == NET_XMIT_SUCCESS) { /* count the sent packet */ switch (packet_subtype) { diff --git a/fragmentation.c b/fragmentation.c index bcc4bea..12811e0 100644 --- a/fragmentation.c +++ b/fragmentation.c @@ -354,8 +354,7 @@ bool batadv_frag_skb_fwd(struct sk_buff *skb, skb->len + ETH_HLEN);

packet->ttl--; - batadv_send_skb_packet(skb, neigh_node->if_incoming, - neigh_node->addr); + batadv_send_unicast_skb(skb, neigh_node); ret = true; }

@@ -461,8 +460,7 @@ bool batadv_frag_send_packet(struct sk_buff *skb, batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_TX); batadv_add_counter(bat_priv, BATADV_CNT_FRAG_TX_BYTES, skb_fragment->len + ETH_HLEN); - batadv_send_skb_packet(skb_fragment, neigh_node->if_incoming, - neigh_node->addr); + batadv_send_unicast_skb(skb_fragment, neigh_node); frag_header.no++;

/* The initial check in this function should cover this case */ @@ -481,7 +479,7 @@ bool batadv_frag_send_packet(struct sk_buff *skb, batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_TX); batadv_add_counter(bat_priv, BATADV_CNT_FRAG_TX_BYTES, skb->len + ETH_HLEN); - batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + batadv_send_unicast_skb(skb, neigh_node);

return true; out_err: diff --git a/icmp_socket.c b/icmp_socket.c index bf07dfd..4734e02 100644 --- a/icmp_socket.c +++ b/icmp_socket.c @@ -253,7 +253,7 @@ static ssize_t batadv_socket_write(struct file *file, const char __user *buff,

ether_addr_copy(icmp_header->orig, primary_if->net_dev->dev_addr);

- batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); + batadv_send_unicast_skb(skb, neigh_node); goto out;

dst_unreach: diff --git a/network-coding.c b/network-coding.c index a9546fe..bbb4ac0 100644 --- a/network-coding.c +++ b/network-coding.c @@ -535,9 +535,7 @@ batadv_nc_hash_find(struct batadv_hashtable *hash, */ static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet) { - batadv_send_skb_packet(nc_packet->skb, - nc_packet->neigh_node->if_incoming, - nc_packet->nc_path->next_hop); + batadv_send_unicast_skb(nc_packet->skb, nc_packet->neigh_node); nc_packet->skb = NULL; batadv_nc_packet_free(nc_packet); } @@ -1018,11 +1016,11 @@ static bool batadv_nc_code_packets(struct batadv_priv *bat_priv, struct batadv_unicast_packet *packet1; struct batadv_unicast_packet *packet2; struct batadv_coded_packet *coded_packet; - struct batadv_neigh_node *neigh_tmp, *router_neigh; - struct batadv_neigh_node *router_coding = NULL; + struct batadv_neigh_node *neigh_tmp, *router_neigh, *first_dest; + struct batadv_neigh_node *router_coding = NULL, *second_dest; struct batadv_neigh_ifinfo *router_neigh_ifinfo = NULL; struct batadv_neigh_ifinfo *router_coding_ifinfo = NULL; - uint8_t *first_source, *first_dest, *second_source, *second_dest; + uint8_t *first_source, *second_source; __be32 packet_id1, packet_id2; size_t count; bool res = false; @@ -1065,9 +1063,9 @@ static bool batadv_nc_code_packets(struct batadv_priv *bat_priv, */ if (tq_weighted_neigh >= tq_weighted_coding) { /* Destination from nc_packet is selected for MAC-header */ - first_dest = nc_packet->nc_path->next_hop; + first_dest = nc_packet->neigh_node; first_source = nc_packet->nc_path->prev_hop; - second_dest = neigh_node->addr; + second_dest = neigh_node; second_source = ethhdr->h_source; packet1 = (struct batadv_unicast_packet *)nc_packet->skb->data; packet2 = (struct batadv_unicast_packet *)skb->data; @@ -1076,9 +1074,9 @@ static bool batadv_nc_code_packets(struct batadv_priv *bat_priv, skb->data + sizeof(*packet2)); } else { /* Destination for skb is selected for MAC-header */ - first_dest = neigh_node->addr; + first_dest = neigh_node; first_source = ethhdr->h_source; - second_dest = nc_packet->nc_path->next_hop; + second_dest = nc_packet->neigh_node; second_source = nc_packet->nc_path->prev_hop; packet1 = (struct batadv_unicast_packet *)skb->data; packet2 = (struct batadv_unicast_packet *)nc_packet->skb->data; @@ -1175,7 +1173,7 @@ static bool batadv_nc_code_packets(struct batadv_priv *bat_priv, batadv_nc_packet_free(nc_packet);

/* Send the coded packet and return true */ - batadv_send_skb_packet(skb_dest, neigh_node->if_incoming, first_dest); + batadv_send_unicast_skb(skb_dest, first_dest); res = true; out: if (router_neigh) diff --git a/send.c b/send.c index 63a46c3..734b24e 100644 --- a/send.c +++ b/send.c @@ -30,16 +30,30 @@

static void batadv_send_outstanding_bcast_packet(struct work_struct *work);

-/* send out an already prepared packet to the given address via the - * specified batman interface +/** + * batadv_send_skb_packet - send an already prepared packet + * @skb: the packet to send + * @hard_iface: the interface to use to send the broadcast packet + * @neigh_node: the destination node. If not NULL packet is sent as unicast + * + * Send out an already prepared packet to the given neighbor or broadcast it + * using the specified interface. Either hard_iface or neigh_node must be not + * NULL. + * If neigh_node is NULL, then the packet is broadcasted using hard_iface, + * otherwise it is sent as unicast to the given neighbor. + * + * Return NET_TX_DROP in case of error or the result of dev_queue_xmit(skb) + * otherwise */ int batadv_send_skb_packet(struct sk_buff *skb, struct batadv_hard_iface *hard_iface, const uint8_t *dst_addr) { - struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); + struct batadv_priv *bat_priv; struct ethhdr *ethhdr;

+ bat_priv = netdev_priv(hard_iface->soft_iface); + if (hard_iface->if_status != BATADV_IF_ACTIVE) goto send_skb_err;

@@ -81,6 +95,26 @@ send_skb_err: return NET_XMIT_DROP; }

+int batadv_send_broadcast_skb(struct sk_buff *skb, + struct batadv_hard_iface *hard_iface) +{ + return batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); +} + +int batadv_send_unicast_skb(struct sk_buff *skb, + struct batadv_neigh_node *neigh) +{ + int ret; + + ret = batadv_send_skb_packet(skb, neigh->if_incoming, neigh->addr); +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + if (ret != NET_XMIT_DROP && neigh->elp_neigh) + neigh->elp_neigh->last_unicast_tx = jiffies; +#endif + + return ret; +} + /** * batadv_send_skb_to_orig - Lookup next-hop and transmit skb. * @skb: Packet to be transmitted. @@ -127,8 +161,7 @@ int batadv_send_skb_to_orig(struct sk_buff *skb, if (recv_if && batadv_nc_skb_forward(skb, neigh_node)) { ret = NET_XMIT_POLICED; } else { - batadv_send_skb_packet(skb, neigh_node->if_incoming, - neigh_node->addr); + batadv_send_unicast_skb(skb, neigh_node); ret = NET_XMIT_SUCCESS; }

@@ -516,8 +549,7 @@ static void batadv_send_outstanding_bcast_packet(struct work_struct *work) /* send a copy of the saved skb */ skb1 = skb_clone(forw_packet->skb, GFP_ATOMIC); if (skb1) - batadv_send_skb_packet(skb1, hard_iface, - batadv_broadcast_addr); + batadv_send_broadcast_skb(skb1, hard_iface); } rcu_read_unlock();

diff --git a/send.h b/send.h index 20e1668..f510dee 100644 --- a/send.h +++ b/send.h @@ -18,12 +18,16 @@ #ifndef _NET_BATMAN_ADV_SEND_H_ #define _NET_BATMAN_ADV_SEND_H_

-int batadv_send_skb_packet(struct sk_buff *skb, - struct batadv_hard_iface *hard_iface, - const uint8_t *dst_addr); int batadv_send_skb_to_orig(struct sk_buff *skb, struct batadv_orig_node *orig_node, struct batadv_hard_iface *recv_if); +int batadv_send_skb_packet(struct sk_buff *skb, + struct batadv_hard_iface *hard_iface, + const uint8_t *dst_addr); +int batadv_send_broadcast_skb(struct sk_buff *skb, + struct batadv_hard_iface *hard_iface); +int batadv_send_unicast_skb(struct sk_buff *skb, + struct batadv_neigh_node *neigh_node); void batadv_schedule_bat_ogm(struct batadv_hard_iface *hard_iface); int batadv_add_bcast_packet_to_list(struct batadv_priv *bat_priv, const struct sk_buff *skb, diff --git a/types.h b/types.h index 22d621e..54fae29 100644 --- a/types.h +++ b/types.h @@ -342,6 +342,7 @@ struct batadv_gw_node { * @metric: ewma link metric towards this neighbor * @last_recv_seqno: last ELP received sequence number * @lest_seen: last time this neigh has been seen + * @last_unicast_tx: when the last unicast packet has been sent to this neighbor * @refcount: number of contexts the object is used * @rcu: struct used for freeing in an RCU-safe manner */ @@ -353,6 +354,7 @@ struct batadv_elp_neigh_node { uint32_t last_recv_seqno; unsigned long last_seen; uint32_t elp_interval; + unsigned long last_unicast_tx; atomic_t refcount; struct rcu_head rcu; };

From: Antonio Quartulli antonio@open-mesh.com

Improve the neighbour purging routine to timely detect when a neighbour is not sending data anymore without waiting for a real timeout. This detection system can be used by the B.A.T.M.A.N. V routing algorithm to trigger an on-demand route reconstruction.

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v.c | 7 +++++ bat_v_elp.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- bat_v_elp.h | 2 ++ types.h | 2 ++ 4 files changed, 98 insertions(+), 4 deletions(-)

diff --git a/bat_v.c b/bat_v.c index 3aa42ec..5681d19 100644 --- a/bat_v.c +++ b/bat_v.c @@ -75,14 +75,21 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = {

int batadv_v_mesh_init(struct batadv_priv *bat_priv) { + int r; + atomic_set(&bat_priv->bat_v.base_throughput, BATADV_DEFAULT_BASE_THROUGHPUT);

+ r = batadv_v_elp_init(bat_priv); + if (r) + return r; + return batadv_v_ogm_init(bat_priv); }

void batadv_v_mesh_free(struct batadv_priv *bat_priv) { + batadv_v_elp_free(bat_priv); batadv_v_ogm_free(bat_priv); }

diff --git a/bat_v_elp.c b/bat_v_elp.c index 31190af..763113e 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -25,6 +25,7 @@ #include "send.h" #include "bat_algo.h" #include "bat_v_elp.h" +#include "bat_v_ogm.h" #include "originator.h" #include "routing.h" #include "soft-interface.h" @@ -186,30 +187,55 @@ batadv_v_elp_neigh_get(struct batadv_hard_iface *hard_iface, * batadv_v_elp_neigh_purge - purge obsolete neighbour nodes * * Deletes the ELP neighbour nodes that did not send any ELP message for a - * pre-defined amount of time. + * pre-defined amount of time and returns the minimum ELP interval among all the + * remaining neighbours. */ -static void batadv_v_elp_neigh_purge(struct batadv_hard_iface *hard_iface) +static uint32_t batadv_v_elp_neigh_purge(struct batadv_hard_iface *hard_iface) { + struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); unsigned long timeout; struct batadv_elp_neigh_node *neigh; struct hlist_node *node; bool has_timed_out; + uint32_t tmp_interval, min_interval = UINT_MAX;

spin_lock_bh(&hard_iface->bat_v.neigh_list_lock); hlist_for_each_entry_safe(neigh, node, &hard_iface->bat_v.neigh_list, list) { - timeout = neigh->elp_interval * BATADV_ELP_OUTDATED_MAX; + tmp_interval = neigh->elp_interval; + + timeout = tmp_interval * BATADV_ELP_OUTDATED_MAX; has_timed_out = batadv_has_timed_out(neigh->last_seen, timeout); + if (has_timed_out) { + /* this neigh is dead! the node could react somehow. + * TODO: implement dead node reaction mechanism + */ + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Node %pM is dead.\n", neigh->addr);

+ /* this node is not sending ELP packets anymore. Don't + * consider it in the minimum ELP interval research + */ + tmp_interval = UINT_MAX; + } + + has_timed_out = batadv_has_timed_out(neigh->last_seen, + BATADV_PURGE_TIMEOUT); if ((!has_timed_out) && - (hard_iface->if_status == BATADV_IF_ACTIVE)) + (hard_iface->if_status == BATADV_IF_ACTIVE)) { + if (tmp_interval < min_interval) + min_interval = tmp_interval; continue; + }

hlist_del_rcu(&neigh->list); atomic_dec(&hard_iface->bat_v.num_neighbors); batadv_elp_neigh_node_free_ref(neigh); + } spin_unlock_bh(&hard_iface->bat_v.neigh_list_lock); + + return min_interval; }

/** @@ -479,6 +505,7 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,

{ struct batadv_elp_neigh_node *neigh; + uint32_t interval;

neigh = batadv_v_elp_neigh_get(if_incoming, neigh_addr); if (!neigh) { @@ -490,6 +517,16 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,

neigh->last_seen = jiffies; neigh->last_recv_seqno = ntohl(elp_packet->seqno); + neigh->elp_interval = ntohl(elp_packet->elp_interval); + + interval = atomic_read(&bat_priv->bat_v.neigh_interval); + if (neigh->elp_interval >= interval) + goto out; + + /* got a shorter elp interval: reschedule the neigh check */ + atomic_set(&bat_priv->bat_v.neigh_interval, neigh->elp_interval); + queue_delayed_work(batadv_event_workqueue, &bat_priv->bat_v.neigh_wq, + msecs_to_jiffies(neigh->elp_interval));

out: if (neigh) @@ -625,3 +662,49 @@ out: batadv_hardif_free_ref(primary_if); return 0; } + +static void batadv_v_elp_check_neigh(struct work_struct *work) +{ + struct batadv_priv_bat_v *bat_v; + struct batadv_priv *bat_priv; + struct batadv_hard_iface *hard_iface; + uint32_t tmp_interval, min_interval = UINT_MAX; + + bat_v = container_of(work, struct batadv_priv_bat_v, neigh_wq.work); + bat_priv = container_of(bat_v, struct batadv_priv, bat_v); + + list_for_each_entry(hard_iface, &batadv_hardif_list, list) { + if (hard_iface->soft_iface != bat_priv->soft_iface) + continue; + + tmp_interval = batadv_v_elp_neigh_purge(hard_iface); + /* while iterating over all the ELP neighbors, find the smallest + * ELP interval to use to schedule the next check + */ + if (tmp_interval < min_interval) + min_interval = tmp_interval; + } + + /* if there are no more ELP neighbors the work does not need to be + * rescheduled + */ + if (min_interval == UINT_MAX) + return; + + atomic_set(&bat_priv->bat_v.neigh_interval, min_interval); + queue_delayed_work(batadv_event_workqueue, &bat_priv->bat_v.neigh_wq, + msecs_to_jiffies(min_interval)); +} + +int batadv_v_elp_init(struct batadv_priv *bat_priv) +{ + INIT_DELAYED_WORK(&bat_priv->bat_v.neigh_wq, batadv_v_elp_check_neigh); + atomic_set(&bat_priv->bat_v.neigh_interval, UINT_MAX); + + return 0; +} + +void batadv_v_elp_free(struct batadv_priv *bat_priv) +{ + cancel_delayed_work_sync(&bat_priv->bat_v.neigh_wq); +} diff --git a/bat_v_elp.h b/bat_v_elp.h index 4f34ecb..5dd0568 100644 --- a/bat_v_elp.h +++ b/bat_v_elp.h @@ -33,5 +33,7 @@ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *hard_iface); int batadv_v_elp_packet_recv(struct sk_buff *skb, struct batadv_hard_iface *if_incoming); int batadv_v_elp_seq_print_text(struct seq_file *seq, void *offset); +int batadv_v_elp_init(struct batadv_priv *bat_priv); +void batadv_v_elp_free(struct batadv_priv *bat_priv);

#endif /* _NET_BATMAN_ADV_BAT_V_ELP_H_ */ diff --git a/types.h b/types.h index 6f05d99..2ba27ab 100644 --- a/types.h +++ b/types.h @@ -748,6 +748,8 @@ struct batadv_priv_bat_v { struct delayed_work ogm_wq; atomic_t ogm_seqno; atomic_t base_throughput; + atomic_t neigh_interval; + struct delayed_work neigh_wq; };

/**

From: Antonio Quartulli antonio@open-mesh.com

This API has to be used to let any routing protocol free neighbor specific allocated resources

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- originator.c | 6 ++++++ types.h | 2 ++ 2 files changed, 8 insertions(+)

diff --git a/originator.c b/originator.c index 447f417..5670df8 100644 --- a/originator.c +++ b/originator.c @@ -196,13 +196,19 @@ static void batadv_neigh_node_free_rcu(struct rcu_head *rcu) struct hlist_node *node_tmp; struct batadv_neigh_node *neigh_node; struct batadv_neigh_ifinfo *neigh_ifinfo; + struct batadv_algo_ops *bao;

neigh_node = container_of(rcu, struct batadv_neigh_node, rcu); + bao = neigh_node->orig_node->bat_priv->bat_algo_ops;

hlist_for_each_entry_safe(neigh_ifinfo, node_tmp, &neigh_node->ifinfo_list, list) { batadv_neigh_ifinfo_free_ref_now(neigh_ifinfo); } + + if (bao->bat_neigh_free) + bao->bat_neigh_free(neigh_node); + batadv_hardif_free_ref_now(neigh_node->if_incoming);

kfree(neigh_node); diff --git a/types.h b/types.h index a51921e..df1479e 100644 --- a/types.h +++ b/types.h @@ -1203,6 +1203,8 @@ struct batadv_algo_ops { int max_if_num); int (*bat_orig_del_if)(struct batadv_orig_node *orig_node, int max_if_num, int del_if_num); + /* neigh_node handling API */ + void (*bat_neigh_free)(struct batadv_neigh_node *neigh); };

/**

From: Antonio Quartulli antonio@open-mesh.com

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+)

diff --git a/bat_v.c b/bat_v.c index 3e4575d..70ff9e9 100644 --- a/bat_v.c +++ b/bat_v.c @@ -21,6 +21,7 @@ #include "bat_algo.h" #include "bat_v_elp.h" #include "bat_v_ogm.h" +#include "originator.h"

static int batadv_v_iface_enable(struct batadv_hard_iface *hard_iface) { @@ -63,6 +64,23 @@ static void batadv_v_ogm_emit(struct batadv_forw_packet *forw_packet) { }

+static bool batadv_v_neigh_is_eob(struct batadv_neigh_node *neigh1, + struct batadv_hard_iface *if_outgoing1, + struct batadv_neigh_node *neigh2, + struct batadv_hard_iface *if_outgoing2) +{ + struct batadv_neigh_ifinfo *ifinfo1, *ifinfo2; + uint32_t threshold; + + ifinfo1 = batadv_neigh_ifinfo_get(neigh1, if_outgoing1); + ifinfo2 = batadv_neigh_ifinfo_get(neigh2, if_outgoing2); + + threshold = ifinfo1->bat_v.metric << 8 >> 10; + threshold = ifinfo1->bat_v.metric - threshold; + + return ifinfo2->bat_v.metric > threshold; +} + static void batadv_v_neigh_free(struct batadv_neigh_node *neigh) { batadv_elp_neigh_node_free_ref(neigh->bat_v.elp_neigh); @@ -77,6 +95,7 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = { .bat_primary_iface_set = batadv_v_primary_iface_set, .bat_ogm_emit = batadv_v_ogm_emit, .bat_ogm_schedule = batadv_v_ogm_schedule, + .bat_neigh_is_equiv_or_better = batadv_v_neigh_is_eob, .bat_neigh_free = batadv_v_neigh_free, };

From: Antonio Quartulli antonio@open-mesh.com

Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 98 insertions(+)

diff --git a/bat_v.c b/bat_v.c index d05d548..6b21afe 100644 --- a/bat_v.c +++ b/bat_v.c @@ -64,6 +64,103 @@ static void batadv_v_ogm_emit(struct batadv_forw_packet *forw_packet) { }

+/** + * batadv_v_orig_print_neigh - print neighbors for the originator table + * @orig_node: the orig_node for which the neighbors are printed + * @if_outgoing: outgoing interface for these entries + * @seq: debugfs table seq_file struct + * + * Must be called while holding an rcu lock. + */ +static void +batadv_v_orig_print_neigh(struct batadv_orig_node *orig_node, + struct batadv_hard_iface *if_outgoing, + struct seq_file *seq) +{ + struct batadv_neigh_node *neigh_node; + struct batadv_neigh_ifinfo *n_ifinfo; + + hlist_for_each_entry_rcu(neigh_node, &orig_node->neigh_list, list) { + n_ifinfo = batadv_neigh_ifinfo_get(neigh_node, if_outgoing); + if (!n_ifinfo) + continue; + + seq_printf(seq, " %pM (%9u.%1u)", + neigh_node->addr, + n_ifinfo->bat_v.metric / 10, + n_ifinfo->bat_v.metric % 10); + + batadv_neigh_ifinfo_free_ref(n_ifinfo); + } +} + +/** + * batadv_v_orig_print - print the originator table + * @bat_priv: the bat priv with all the soft interface information + * @seq: debugfs table seq_file struct + * @if_outgoing: the outgoing interface for which this should be printed + */ +static void batadv_v_orig_print(struct batadv_priv *bat_priv, + struct seq_file *seq, + struct batadv_hard_iface *if_outgoing) +{ + struct batadv_neigh_node *neigh_node; + struct batadv_hashtable *hash = bat_priv->orig_hash; + int last_seen_msecs, last_seen_secs; + struct batadv_orig_node *orig_node; + struct batadv_neigh_ifinfo *n_ifinfo; + unsigned long last_seen_jiffies; + struct hlist_head *head; + int batman_count = 0; + uint32_t i; + + seq_printf(seq, " %-15s %s (%11s) %17s [%10s]: %20s ...\n", + "Originator", "last-seen", "metric", "Nexthop", + "outgoingIF", "Potential nexthops"); + + for (i = 0; i < hash->size; i++) { + head = &hash->table[i]; + + rcu_read_lock(); + hlist_for_each_entry_rcu(orig_node, head, hash_entry) { + neigh_node = batadv_orig_router_get(orig_node, + if_outgoing); + if (!neigh_node) + continue; + + n_ifinfo = batadv_neigh_ifinfo_get(neigh_node, + if_outgoing); + if (!n_ifinfo) + goto next; + + last_seen_jiffies = jiffies - orig_node->last_seen; + last_seen_msecs = jiffies_to_msecs(last_seen_jiffies); + last_seen_secs = last_seen_msecs / 1000; + last_seen_msecs = last_seen_msecs % 1000; + + seq_printf(seq, "%pM %4i.%03is (%9u.%1u) %pM [%10s]:", + orig_node->orig, last_seen_secs, + last_seen_msecs, n_ifinfo->bat_v.metric / 10, + n_ifinfo->bat_v.metric % 10, + neigh_node->addr, + neigh_node->if_incoming->net_dev->name); + + batadv_v_orig_print_neigh(orig_node, if_outgoing, seq); + seq_puts(seq, "\n"); + batman_count++; + +next: + batadv_neigh_node_free_ref(neigh_node); + if (n_ifinfo) + batadv_neigh_ifinfo_free_ref(n_ifinfo); + } + rcu_read_unlock(); + } + + if (batman_count == 0) + seq_puts(seq, "No batman nodes in range ...\n"); +} + static int batadv_v_neigh_cmp(struct batadv_neigh_node *neigh1, struct batadv_hard_iface *if_outgoing1, struct batadv_neigh_node *neigh2, @@ -112,6 +209,7 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = { .bat_primary_iface_set = batadv_v_primary_iface_set, .bat_ogm_emit = batadv_v_ogm_emit, .bat_ogm_schedule = batadv_v_ogm_schedule, + .bat_orig_print = batadv_v_orig_print, .bat_neigh_cmp = batadv_v_neigh_cmp, .bat_neigh_is_equiv_or_better = batadv_v_neigh_is_eob, .bat_neigh_free = batadv_v_neigh_free,