Hi,
after numerous infrastructure changes in the past weeks ELP[1] slowly approaches the state in which it can be tested and later merged into the master branch.
Since its initial implementation by Linus Luessing last summer a lot has happened: * the internal protocol name (NDP) was renamed to ELP * the old code was rebased on top of the master branch * the ELP code was adjusted to the many changes in our code base * several patches were squashed together * brought the code in sync with the spec * numerous bugs were fixed (buffer overflow, writing into random memory sections, memory corruptions, locking issues, elp packet length checks, printing the neighbors of the requested mesh only and many more)
The ELP code is the first to use the recently introduced routing protocol abstraction. It is not compiled into batman-adv by default, therefore you need to compile with CONFIG_BATMAN_ADV_BATMAN_V=y or modify the makefile.
Once the batman-adv kernel module has been loaded you can check for the existence of the new routing protocol:
cat /sys/kernel/debug/batman_adv/routing_algos Available routing algorithms: BATMAN IV BATMAN V
To activate B.A.T.M.A.N. V (ELP) you should run the following command *before* adding any interface via batctl:
echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo
Caveats: * ELP alone (without OGMv2) isn't very useful because ELP handles single hop neighbors only. So don't expect to convert your entire mesh network to B.A.T.M.A.N. V just yet. * The batman-adv routing protocol abstraction still lacks the translation table integration which is why the following patches will lead to a kernel crash. The ELP repository[2] contains a patch to disable the TT propagation partially to mitigate the problem until a proper solution has been implemented.
Any comments and suggestions are appreciated.
Regards, Marek
[1] http://www.open-mesh.org/wiki/batman-adv/ELP [2] http://git.open-mesh.org/?p=marek/batman-adv.git;a=shortlog;h=refs/heads/elp
Linus Luessing (5): batman-adv: ELP - adding basic infrastructure batman-adv: ELP - creating neighbor structures, updating LQs batman-adv: ELP - exporting neighbor list via debugfs batman-adv: ELP - adding sysfs parameter for elp interval batman-adv: ELP - add configurable minimum ELP packet length (def: 300B)
Makefile | 2 + Makefile.kbuild | 1 + README.external | 1 + bat_algo.h | 6 + bat_debugfs.c | 16 ++ bat_sysfs.c | 8 + bat_v_elp.c | 500 ++++++++++++++++++++++++++++++++++++++++++++ gen-compat-autoconf.sh | 1 + hard-interface.c | 7 + main.c | 1 + packet.h | 20 ++- sysfs-class-net-batman-adv | 13 ++ types.h | 15 ++ 13 files changed, 590 insertions(+), 1 deletions(-)
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 --- Makefile | 2 + Makefile.kbuild | 1 + README.external | 1 + bat_algo.h | 6 ++ bat_v_elp.c | 175 ++++++++++++++++++++++++++++++++++++++++++++++++ gen-compat-autoconf.sh | 1 + hard-interface.c | 6 ++ main.c | 1 + packet.h | 14 ++++- types.h | 6 ++ 10 files changed, 212 insertions(+), 1 deletions(-) create mode 100644 bat_v_elp.c
diff --git a/Makefile b/Makefile index ac84fba..3d08354 100644 --- a/Makefile +++ b/Makefile @@ -25,6 +25,8 @@ export CONFIG_BATMAN_ADV_DEBUG=n export CONFIG_BATMAN_ADV_BLA=y # B.A.T.M.A.N. distributed ARP table: export CONFIG_BATMAN_ADV_DAT=y +# 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 ad002cd..dcffb7f 100644 --- a/Makefile.kbuild +++ b/Makefile.kbuild @@ -21,6 +21,7 @@ obj-$(CONFIG_BATMAN_ADV) += batman-adv.o batman-adv-y += bat_debugfs.o batman-adv-y += bat_iv_ogm.o +batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v_elp.o batman-adv-y += bat_sysfs.o batman-adv-y += bitarray.o batman-adv-$(CONFIG_BATMAN_ADV_BLA) += bridge_loop_avoidance.o diff --git a/README.external b/README.external index 95a7eb4..f1ec46a 100644 --- a/README.external +++ b/README.external @@ -38,6 +38,7 @@ module). Available options and their possible values are * CONFIG_BATMAN_ADV_DEBUG=[y|n*] (B.A.T.M.A.N. debugging) * 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_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 9852a68..2932082 100644 --- a/bat_algo.h +++ b/bat_algo.h @@ -24,4 +24,10 @@
int bat_iv_init(void);
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V +int bat_v_init(void); +#else +#define bat_v_init(...) {} +#endif /* CONFIG_BATMAN_ADV_BATMAN_V */ + #endif /* _NET_BATMAN_ADV_BAT_ALGO_H_ */ diff --git a/bat_v_elp.c b/bat_v_elp.c new file mode 100644 index 0000000..c2dee5c --- /dev/null +++ b/bat_v_elp.c @@ -0,0 +1,175 @@ +/* + * Copyright (C) 2011-2012 B.A.T.M.A.N. contributors: + * + * Linus Lüssing, Marek Lindner + * + * 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" + +static void bat_v_elp_start_timer(struct hard_iface *hard_iface) +{ + unsigned long elp_interval; + + elp_interval = msecs_to_jiffies(atomic_read(&hard_iface->elp_interval) + - JITTER + (random32() % 2 * JITTER)); + + queue_delayed_work(bat_event_workqueue, + &hard_iface->elp_wq, elp_interval); +} + +static void bat_v_elp_send_outstanding(struct work_struct *work) +{ + struct hard_iface *hard_iface; + struct bat_priv *bat_priv; + struct batman_elp_packet *elp_packet; + struct sk_buff *skb; + + hard_iface = container_of(work, struct hard_iface, elp_wq.work); + bat_priv = netdev_priv(hard_iface->soft_iface); + + if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING) + goto out; + + if ((hard_iface->if_status == IF_NOT_IN_USE) || + (hard_iface->if_status == IF_TO_BE_REMOVED)) + goto out; + + /* the interface was enabled but may not be ready yet */ + if (hard_iface->if_status != IF_ACTIVE) + goto restart_timer; + + skb = skb_copy(hard_iface->elp_skb, GFP_ATOMIC); + if (!skb) + goto out; + + elp_packet = (struct batman_elp_packet *)skb->data; + elp_packet->seqno = htonl(atomic_read(&hard_iface->elp_seqno)); + elp_packet->num_neighbors = 0; + + bat_dbg(DBG_BATMAN, bat_priv, + "Sending elp packet on interface %s, seqno %d\n", + hard_iface->net_dev->name, atomic_read(&hard_iface->elp_seqno)); + + send_skb_packet(skb, hard_iface, broadcast_addr); + + atomic_inc(&hard_iface->elp_seqno); + bat_v_elp_start_timer(hard_iface); + +out: + return; +} + +static int bat_v_elp_iface_enable(struct hard_iface *hard_iface) +{ + struct batman_elp_packet *elp_packet; + unsigned long random_seqno; + int res = -1; + + INIT_HLIST_HEAD(&hard_iface->neigh_list); + spin_lock_init(&hard_iface->neigh_list_lock); + + hard_iface->elp_skb = dev_alloc_skb(ETH_DATA_LEN + ETH_HLEN); + if (!hard_iface->elp_skb) + goto out; + + skb_reserve(hard_iface->elp_skb, ETH_HLEN + BATMAN_ELP_HLEN); + elp_packet = (struct batman_elp_packet *)skb_push(hard_iface->elp_skb, + BATMAN_ELP_HLEN); + memset(elp_packet, 0, BATMAN_ELP_HLEN); + + elp_packet->header.packet_type = BAT_V_ELP; + elp_packet->header.version = COMPAT_VERSION; + elp_packet->header.ttl = 0; + + /* randomize initial seqno to avoid collision */ + get_random_bytes(&random_seqno, sizeof(unsigned long)); + atomic_set(&hard_iface->elp_seqno, (uint32_t)random_seqno); + + INIT_DELAYED_WORK(&hard_iface->elp_wq, bat_v_elp_send_outstanding); + bat_v_elp_start_timer(hard_iface); + res = 0; + +out: + return res; +} + +static void bat_v_elp_iface_disable(struct hard_iface *hard_iface) +{ + cancel_delayed_work_sync(&hard_iface->elp_wq); + + dev_kfree_skb(hard_iface->elp_skb); + hard_iface->elp_skb = NULL; +} + +static void bat_v_elp_iface_update_mac(struct hard_iface *hard_iface) +{ + return; +} + +static void bat_v_elp_primary_iface_set(struct hard_iface *hard_iface) +{ + struct hard_iface *hard_iface_tmp; + struct batman_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, &hardif_list, list) { + if (hard_iface->soft_iface != hard_iface_tmp->soft_iface) + continue; + + if (!hard_iface_tmp->elp_skb) + continue; + + skb = hard_iface_tmp->elp_skb; + elp_packet = (struct batman_elp_packet *)skb->data; + memcpy(elp_packet->orig, + hard_iface->net_dev->dev_addr, ETH_ALEN); + } + rcu_read_unlock(); +} + +static void bat_v_ogm_schedule(struct hard_iface *hard_iface, + int tt_num_changes) +{ + return; +} + +static void bat_v_ogm_emit(struct forw_packet *forw_packet) +{ + return; +} + + +static struct bat_algo_ops batman_v __read_mostly = { + .name = "BATMAN V", + .bat_iface_enable = bat_v_elp_iface_enable, + .bat_iface_disable = bat_v_elp_iface_disable, + .bat_iface_update_mac = bat_v_elp_iface_update_mac, + .bat_primary_iface_set = bat_v_elp_primary_iface_set, + .bat_ogm_schedule = bat_v_ogm_schedule, + .bat_ogm_emit = bat_v_ogm_emit, +}; + +int __init bat_v_init(void) +{ + return bat_algo_register(&batman_v); +} diff --git a/gen-compat-autoconf.sh b/gen-compat-autoconf.sh index 7ea42aa..f6f32e7 100755 --- a/gen-compat-autoconf.sh +++ b/gen-compat-autoconf.sh @@ -39,6 +39,7 @@ gen_config() { 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_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/hard-interface.c b/hard-interface.c index daa6adc..e53e143 100644 --- a/hard-interface.c +++ b/hard-interface.c @@ -450,6 +450,12 @@ static struct hard_iface *hardif_add_interface(struct net_device *net_dev) atomic_set(&hard_iface->seqno, 1); hard_iface->packet_buff = NULL;
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V + atomic_set(&hard_iface->elp_interval, 500); + atomic_set(&hard_iface->elp_seqno, 1); + hard_iface->elp_skb = NULL; +#endif /* CONFIG_BATMAN_ADV_BATMAN_V */ + return hard_iface;
free_if: diff --git a/main.c b/main.c index 0757c2d..b83a693 100644 --- a/main.c +++ b/main.c @@ -56,6 +56,7 @@ static int __init batman_init(void)
recv_handler_init();
+ bat_v_init(); bat_iv_init();
/* the name should not be longer than 10 chars - see diff --git a/packet.h b/packet.h index 3c4c533..cf516dc 100644 --- a/packet.h +++ b/packet.h @@ -33,7 +33,8 @@ enum bat_packettype { BAT_UNICAST_FRAG = 0x06, BAT_TT_QUERY = 0x07, BAT_ROAM_ADV = 0x08, - BAT_UNICAST_4ADDR = 0x09 + BAT_UNICAST_4ADDR = 0x09, + BAT_V_ELP = 0x10 };
enum bat_subtype { @@ -136,6 +137,17 @@ struct batman_ogm_packet {
#define BATMAN_OGM_HLEN sizeof(struct batman_ogm_packet)
+/* echo location packet */ +struct batman_elp_packet { + struct batman_header header; + uint8_t num_neighbors; + uint32_t seqno; + uint32_t elp_interval; + uint8_t orig[ETH_ALEN]; +} __packed; + +#define BATMAN_ELP_HLEN sizeof(struct batman_elp_packet) + struct icmp_packet { struct batman_header header; uint8_t msg_type; /* see ICMP message types above */ diff --git a/types.h b/types.h index 15f538a..86f2250 100644 --- a/types.h +++ b/types.h @@ -58,6 +58,12 @@ struct hard_iface { struct packet_type batman_adv_ptype; struct net_device *soft_iface; struct rcu_head rcu; +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + atomic_t elp_interval; + atomic_t elp_seqno; + struct sk_buff *elp_skb; + struct delayed_work elp_wq; +#endif /* CONFIG_BATMAN_ADV_BATMAN_V */ };
/**
From: Linus Luessing linus.luessing@web.de
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 --- bat_v_elp.c | 255 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- packet.h | 6 ++ types.h | 8 ++ 3 files changed, 267 insertions(+), 2 deletions(-)
diff --git a/bat_v_elp.c b/bat_v_elp.c index c2dee5c..e252c04 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -23,6 +23,8 @@ #include "hard-interface.h" #include "send.h" #include "bat_algo.h" +#include "originator.h" +#include "routing.h"
static void bat_v_elp_start_timer(struct hard_iface *hard_iface) { @@ -35,12 +37,78 @@ static void bat_v_elp_start_timer(struct hard_iface *hard_iface) &hard_iface->elp_wq, elp_interval); }
+static struct neigh_node *bat_v_elp_neigh_new(struct hard_iface *hard_iface, + uint8_t *neigh_addr, + uint32_t seqno) +{ + struct neigh_node *neigh_node; + + neigh_node = neigh_node_new(hard_iface, neigh_addr, seqno); + if (!neigh_node) + goto out; + + neigh_node->last_recv_seqno = seqno - 1; + + spin_lock_bh(&hard_iface->neigh_list_lock); + hlist_add_head_rcu(&neigh_node->list, &hard_iface->neigh_list); + spin_unlock_bh(&hard_iface->neigh_list_lock); + +out: + return neigh_node; +} + +static struct neigh_node *bat_v_elp_neigh_get(struct hard_iface *hard_iface, + uint8_t *neigh_addr) +{ + struct neigh_node *neigh_node = NULL, *neigh_node_tmp; + struct hlist_node *node; + + rcu_read_lock(); + hlist_for_each_entry_rcu(neigh_node_tmp, node, + &hard_iface->neigh_list, list) { + if (!compare_eth(neigh_node_tmp->addr, neigh_addr)) + continue; + + if (!atomic_inc_not_zero(&neigh_node_tmp->refcount)) + continue; + + neigh_node = neigh_node_tmp; + break; + } + rcu_read_unlock(); + + return neigh_node; +} + +static void bat_v_elp_neigh_purge(struct hard_iface *hard_iface) +{ + struct neigh_node *neigh_node; + struct hlist_node *node, *node_tmp; + + spin_lock_bh(&hard_iface->neigh_list_lock); + hlist_for_each_entry_safe(neigh_node, node, node_tmp, + &hard_iface->neigh_list, list) { + + if ((!has_timed_out(neigh_node->last_seen, PURGE_TIMEOUT)) && + (hard_iface->if_status == IF_ACTIVE)) + continue; + + hlist_del_rcu(&neigh_node->list); + neigh_node_free_ref(neigh_node); + } + spin_unlock_bh(&hard_iface->neigh_list_lock); +} + static void bat_v_elp_send_outstanding(struct work_struct *work) { struct hard_iface *hard_iface; struct bat_priv *bat_priv; struct batman_elp_packet *elp_packet; + struct elp_neigh_entry *elp_neigh_entry; + struct neigh_node *neigh_node; + struct hlist_node *node; struct sk_buff *skb; + unsigned int max_len;
hard_iface = container_of(work, struct hard_iface, elp_wq.work); bat_priv = netdev_priv(hard_iface->soft_iface); @@ -48,6 +116,7 @@ static void bat_v_elp_send_outstanding(struct work_struct *work) if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING) goto out;
+ /* we are in the process of shutting this interface down */ if ((hard_iface->if_status == IF_NOT_IN_USE) || (hard_iface->if_status == IF_TO_BE_REMOVED)) goto out; @@ -56,14 +125,40 @@ static void bat_v_elp_send_outstanding(struct work_struct *work) if (hard_iface->if_status != IF_ACTIVE) goto restart_timer;
+ max_len = min_t(unsigned int, ETH_DATA_LEN, hard_iface->net_dev->mtu); + skb = skb_copy(hard_iface->elp_skb, GFP_ATOMIC); if (!skb) goto out;
+ /* purge outdated entries first */ + bat_v_elp_neigh_purge(hard_iface); + elp_packet = (struct batman_elp_packet *)skb->data; elp_packet->seqno = htonl(atomic_read(&hard_iface->elp_seqno)); elp_packet->num_neighbors = 0;
+ elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1); + + rcu_read_lock(); + hlist_for_each_entry_rcu(neigh_node, node, + &hard_iface->neigh_list, list) { + if (skb->len + sizeof(struct elp_neigh_entry) > max_len) { + if (printk_ratelimit()) + bat_err(hard_iface->net_dev, + "Skipping ELP neigh entries: " + "packet length exhausted\n"); + break; + } + + memcpy(elp_neigh_entry->addr, neigh_node->addr, ETH_ALEN); + elp_neigh_entry->rq = neigh_node->rq; + elp_packet->num_neighbors++; + elp_neigh_entry++; + skb_put(skb, sizeof(struct elp_neigh_entry)); + } + rcu_read_unlock(); + bat_dbg(DBG_BATMAN, bat_priv, "Sending elp packet on interface %s, seqno %d\n", hard_iface->net_dev->name, atomic_read(&hard_iface->elp_seqno)); @@ -71,8 +166,9 @@ static void bat_v_elp_send_outstanding(struct work_struct *work) send_skb_packet(skb, hard_iface, broadcast_addr);
atomic_inc(&hard_iface->elp_seqno); - bat_v_elp_start_timer(hard_iface);
+restart_timer: + bat_v_elp_start_timer(hard_iface); out: return; } @@ -117,6 +213,8 @@ static void bat_v_elp_iface_disable(struct hard_iface *hard_iface)
dev_kfree_skb(hard_iface->elp_skb); hard_iface->elp_skb = NULL; + + bat_v_elp_neigh_purge(hard_iface); }
static void bat_v_elp_iface_update_mac(struct hard_iface *hard_iface) @@ -158,6 +256,143 @@ static void bat_v_ogm_emit(struct forw_packet *forw_packet) return; }
+/* extract my own tq to neighbor from the elp packet */ +static uint8_t bat_v_elp_fetch_tq(uint8_t *my_iface_addr, + struct batman_elp_packet *elp_packet, + int elp_packet_len) +{ + struct elp_neigh_entry *elp_neigh_entry; + uint8_t tq = 0; + int i; + + elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1); + elp_packet_len -= BATMAN_ELP_HLEN; + + for (i = 0; i < elp_packet->num_neighbors; i++) { + if (!compare_eth(my_iface_addr, elp_neigh_entry->addr)) + goto next; + + tq = elp_neigh_entry->rq; + break; + + next: + elp_packet_len -= sizeof(struct elp_neigh_entry); + if (elp_packet_len < 0) + break; + + elp_neigh_entry++; + } + + return tq; +} + +static void bat_v_elp_neigh_update_lq(struct hard_iface *hard_iface, + struct neigh_node *neigh_node, + uint8_t my_tq, uint32_t seqno) +{ + struct bat_priv *bat_priv = netdev_priv(hard_iface->soft_iface); + int32_t seq_diff; + int neigh_packet_count; + bool is_new_seqno; + + seq_diff = seqno - neigh_node->last_recv_seqno; + + is_new_seqno = bit_get_packet(bat_priv, neigh_node->elp_rq_bits, + seq_diff, 1); + if (!is_new_seqno) + return; + + bat_dbg(DBG_BATMAN, bat_priv, + "Updating last_seqno of neighbor %pM: old %d, new %d\n", + neigh_node->addr, neigh_node->last_recv_seqno, seqno); + + /*** + * we only update the tq/last seen/last seqno fields upon + * receival of a newer ELP sequence number + */ + neigh_node->tq = my_tq; + neigh_node->last_seen = jiffies; + neigh_node->last_recv_seqno = seqno; + + neigh_packet_count = bitmap_weight(neigh_node->elp_rq_bits, + TQ_LOCAL_WINDOW_SIZE); + neigh_node->rq = (neigh_packet_count * TQ_MAX_VALUE) / + TQ_LOCAL_WINDOW_SIZE; + + bat_dbg(DBG_BATMAN, bat_priv, + "New rq/tq of neighbor %pM: rq %d, tq %d\n", + neigh_node->addr, neigh_node->rq, neigh_node->tq); +} + +void bat_v_elp_neigh_update(uint8_t *neigh_addr, + struct hard_iface *if_incoming, + struct batman_elp_packet *elp_packet, + int elp_packet_len) +{ + struct neigh_node *neigh_node; + uint8_t my_tq; + + neigh_node = bat_v_elp_neigh_get(if_incoming, neigh_addr); + if (!neigh_node) { + neigh_node = bat_v_elp_neigh_new(if_incoming, neigh_addr, + elp_packet->seqno); + if (!neigh_node) + goto out; + } + + my_tq = bat_v_elp_fetch_tq(if_incoming->net_dev->dev_addr, + elp_packet, elp_packet_len); + + spin_lock_bh(&neigh_node->lq_update_lock); + bat_v_elp_neigh_update_lq(if_incoming, neigh_node, + my_tq, elp_packet->seqno); + spin_unlock_bh(&neigh_node->lq_update_lock); + +out: + if (neigh_node) + neigh_node_free_ref(neigh_node); +} + +static int bat_v_elp_packet_recv(struct sk_buff *skb, + struct hard_iface *if_incoming) +{ + struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface); + struct batman_elp_packet *elp_packet; + struct hard_iface *primary_if; + struct ethhdr *ethhdr; + bool ret; + + ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN); + if (!ret) + return NET_RX_DROP; + + /* did we receive a B.A.T.M.A.N. V ELP packet on an interface + * that does not have B.A.T.M.A.N. V ELP enabled ? */ + if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit) + return NET_RX_DROP; + + primary_if = primary_if_get_selected(bat_priv); + if (!primary_if) + goto out; + + ethhdr = (struct ethhdr *)skb_mac_header(skb); + elp_packet = (struct batman_elp_packet *)skb->data; + + /* our own ELP packet */ + if (compare_eth(primary_if->net_dev->dev_addr, elp_packet->orig)) + goto out; + + elp_packet->seqno = ntohl(elp_packet->seqno); + + bat_v_elp_neigh_update(ethhdr->h_source, if_incoming, + elp_packet, skb_headlen(skb)); + +out: + if (primary_if) + hardif_free_ref(primary_if); + dev_kfree_skb(skb); + return NET_RX_SUCCESS; +}
static struct bat_algo_ops batman_v __read_mostly = { .name = "BATMAN V", @@ -171,5 +406,21 @@ static struct bat_algo_ops batman_v __read_mostly = {
int __init bat_v_init(void) { - return bat_algo_register(&batman_v); + int ret; + + /* batman v echo location protocol packet */ + ret = recv_handler_register(BAT_V_ELP, bat_v_elp_packet_recv); + if (ret < 0) + goto out; + + ret = bat_algo_register(&batman_v); + if (ret < 0) + goto handler_unregister; + + goto out; + +handler_unregister: + recv_handler_unregister(BAT_V_ELP); +out: + return ret; } diff --git a/packet.h b/packet.h index cf516dc..ea1683f 100644 --- a/packet.h +++ b/packet.h @@ -148,6 +148,12 @@ struct batman_elp_packet {
#define BATMAN_ELP_HLEN sizeof(struct batman_elp_packet)
+struct elp_neigh_entry { + uint8_t addr[ETH_ALEN]; + uint8_t rq; + uint8_t align; +} __attribute__((packed)); + struct icmp_packet { struct batman_header header; uint8_t msg_type; /* see ICMP message types above */ diff --git a/types.h b/types.h index 86f2250..abe27dd 100644 --- a/types.h +++ b/types.h @@ -61,6 +61,8 @@ struct hard_iface { #ifdef CONFIG_BATMAN_ADV_BATMAN_V atomic_t elp_interval; atomic_t elp_seqno; + struct hlist_head neigh_list; + spinlock_t neigh_list_lock; struct sk_buff *elp_skb; struct delayed_work elp_wq; #endif /* CONFIG_BATMAN_ADV_BATMAN_V */ @@ -158,6 +160,12 @@ struct neigh_node { struct orig_node *orig_node; struct hard_iface *if_incoming; spinlock_t lq_update_lock; /* protects: tq_recv, tq_index */ +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + uint8_t rq; + uint8_t tq; + uint32_t last_recv_seqno; + DECLARE_BITMAP(elp_rq_bits, TQ_LOCAL_WINDOW_SIZE); +#endif };
#ifdef CONFIG_BATMAN_ADV_BLA
+/* extract my own tq to neighbor from the elp packet */ +static uint8_t bat_v_elp_fetch_tq(uint8_t *my_iface_addr,
struct batman_elp_packet *elp_packet,int elp_packet_len)+{
- struct elp_neigh_entry *elp_neigh_entry;
- uint8_t tq = 0;
- int i;
- elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1);
- elp_packet_len -= BATMAN_ELP_HLEN;
- for (i = 0; i < elp_packet->num_neighbors; i++) {
if (!compare_eth(my_iface_addr, elp_neigh_entry->addr))goto next;tq = elp_neigh_entry->rq;break;- next:
elp_packet_len -= sizeof(struct elp_neigh_entry);if (elp_packet_len < 0)break;elp_neigh_entry++;- }
Hi Marek
I'm personally not a fan of using goto like this. Reminds me of BASIC.
Could this be changed? Maybe first validate elp_packet->num_neighbors matches the packet length, and then skip elp_packet_len check in each iteration of the loop. A normal if then else should then be possible.
Thanks Andrew
On Friday, March 23, 2012 22:52:12 Andrew Lunn wrote:
+/* extract my own tq to neighbor from the elp packet */ +static uint8_t bat_v_elp_fetch_tq(uint8_t *my_iface_addr,
struct batman_elp_packet *elp_packet,int elp_packet_len)+{
- struct elp_neigh_entry *elp_neigh_entry;
- uint8_t tq = 0;
- int i;
- elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1);
- elp_packet_len -= BATMAN_ELP_HLEN;
- for (i = 0; i < elp_packet->num_neighbors; i++) {
if (!compare_eth(my_iface_addr, elp_neigh_entry->addr))goto next;tq = elp_neigh_entry->rq;break;- next:
elp_packet_len -= sizeof(struct elp_neigh_entry);if (elp_packet_len < 0)break;elp_neigh_entry++;- }
I'm personally not a fan of using goto like this. Reminds me of BASIC.
Could this be changed? Maybe first validate elp_packet->num_neighbors matches the packet length, and then skip elp_packet_len check in each iteration of the loop. A normal if then else should then be possible.
Something like this ?
elp_packet_len -= BATMAN_ELP_HLEN; elp_packet_len -= elp_packet->num_neighbors * sizeof(struct elp_neigh_entry; if (elp_packet_len < 0) return;
Cheers, Marek
+static int bat_v_elp_packet_recv(struct sk_buff *skb,
struct hard_iface *if_incoming)+{
- struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
- struct batman_elp_packet *elp_packet;
- struct hard_iface *primary_if;
- struct ethhdr *ethhdr;
- bool ret;
- ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
- if (!ret)
return NET_RX_DROP;- /* did we receive a B.A.T.M.A.N. V ELP packet on an interface
* that does not have B.A.T.M.A.N. V ELP enabled ? */- if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
return NET_RX_DROP;
Hi Marek
I've not looked at the code, but i assume this can happen because there is not a per algorithm receive handler? Maybe it makes sense to have a receive handler in algo structure, which can handle per algorithm receive functions? The common PDUs can be handled first and then a call into the algo receive function made to dispatch algo specific PDUs.
Andrew
On Fri, Mar 23, 2012 at 10:22:33 +0100, Andrew Lunn wrote:
+static int bat_v_elp_packet_recv(struct sk_buff *skb,
struct hard_iface *if_incoming)+{
- struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
- struct batman_elp_packet *elp_packet;
- struct hard_iface *primary_if;
- struct ethhdr *ethhdr;
- bool ret;
- ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
- if (!ret)
return NET_RX_DROP;- /* did we receive a B.A.T.M.A.N. V ELP packet on an interface
* that does not have B.A.T.M.A.N. V ELP enabled ? */- if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
return NET_RX_DROP;Hi Marek
I've not looked at the code, but i assume this can happen because there is not a per algorithm receive handler? Maybe it makes sense to have a receive handler in algo structure, which can handle per algorithm receive functions? The common PDUs can be handled first and then a call into the algo receive function made to dispatch algo specific PDUs.
Does this mean that you want to support multiple algorithms at the same time? I don't think it is a good idea..
Cheers,
On Sat, Mar 24, 2012 at 09:14:08AM +0100, Antonio Quartulli wrote:
On Fri, Mar 23, 2012 at 10:22:33 +0100, Andrew Lunn wrote:
+static int bat_v_elp_packet_recv(struct sk_buff *skb,
struct hard_iface *if_incoming)+{
- struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
- struct batman_elp_packet *elp_packet;
- struct hard_iface *primary_if;
- struct ethhdr *ethhdr;
- bool ret;
- ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
- if (!ret)
return NET_RX_DROP;- /* did we receive a B.A.T.M.A.N. V ELP packet on an interface
* that does not have B.A.T.M.A.N. V ELP enabled ? */- if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
return NET_RX_DROP;Hi Marek
I've not looked at the code, but i assume this can happen because there is not a per algorithm receive handler? Maybe it makes sense to have a receive handler in algo structure, which can handle per algorithm receive functions? The common PDUs can be handled first and then a call into the algo receive function made to dispatch algo specific PDUs.
Does this mean that you want to support multiple algorithms at the same time? I don't think it is a good idea..
I'm assuming the choice of algorithm is linked to the soft interface, i.e, bat0 could be using a different algorithm to bat1. So i think multiple algorithms are possible at the same time.
I have been thinking about this a bit more, and also about this bit of code:
+ elp_packet = (struct batman_elp_packet *)skb_push(hard_iface->elp_skb, + BATMAN_ELP_HLEN); + memset(elp_packet, 0, BATMAN_ELP_HLEN); + + elp_packet->header.packet_type = BAT_V_ELP; + elp_packet->header.version = COMPAT_VERSION; + elp_packet->header.ttl = 0;
Marek, what are your plans for COMPAT_VERSION? Will there be a COMPAT_VERSION_IV and COMPAT_VERSION_V sometime soon?
Maybe when registering a receive function, you can pass both the packet_type and version. So a received ELP packet with COMPAT_VERSION_IV would automatically get tossed away, and an ELP with COMPAT_VERSION_V would get dispatched.
Andrew
On Saturday, March 24, 2012 22:21:17 Andrew Lunn wrote:
I'm assuming the choice of algorithm is linked to the soft interface, i.e, bat0 could be using a different algorithm to bat1. So i think multiple algorithms are possible at the same time.
Correct.
I have been thinking about this a bit more, and also about this bit of code:
elp_packet = (struct batman_elp_packet*)skb_push(hard_iface->elp_skb, + BATMAN_ELP_HLEN); + memset(elp_packet, 0, BATMAN_ELP_HLEN);
elp_packet->header.packet_type = BAT_V_ELP;elp_packet->header.version = COMPAT_VERSION;elp_packet->header.ttl = 0;Marek, what are your plans for COMPAT_VERSION? Will there be a COMPAT_VERSION_IV and COMPAT_VERSION_V sometime soon?
Currently, that is not planned. We hoped to keep the compat numbers in sync across the various protocols. Otherwise we all could end up in compat hell.
Maybe when registering a receive function, you can pass both the packet_type and version. So a received ELP packet with COMPAT_VERSION_IV would automatically get tossed away, and an ELP with COMPAT_VERSION_V would get dispatched.
What would be the use case of ELP COMPAT_VERSION_IV vs ELP COMPAT_VERSION_V ? BATMAN IV does not have ELP at all .. maybe I misunderstand ?
Regards, Marek
I have been thinking about this a bit more, and also about this bit of code:
elp_packet = (struct batman_elp_packet*)skb_push(hard_iface->elp_skb, + BATMAN_ELP_HLEN); + memset(elp_packet, 0, BATMAN_ELP_HLEN);
elp_packet->header.packet_type = BAT_V_ELP;elp_packet->header.version = COMPAT_VERSION;elp_packet->header.ttl = 0;Marek, what are your plans for COMPAT_VERSION? Will there be a COMPAT_VERSION_IV and COMPAT_VERSION_V sometime soon?
Currently, that is not planned. We hoped to keep the compat numbers in sync across the various protocols. Otherwise we all could end up in compat hell.
Can they be kept in sync? I would assume that IV is becoming more and more stable, with more effort going into V. So IV is less probable to need an COMPAT increment than V. The three month kernel cycle helps with the sync, but it would be a PITA to have to upgrade an entire IV net because V have forced a COMPAT increment, but IV has not changed and is compatible.
Maybe when registering a receive function, you can pass both the packet_type and version. So a received ELP packet with COMPAT_VERSION_IV would automatically get tossed away, and an ELP with COMPAT_VERSION_V would get dispatched.
What would be the use case of ELP COMPAT_VERSION_IV vs ELP COMPAT_VERSION_V ? BATMAN IV does not have ELP at all .. maybe I misunderstand ?
The COMPAT_VERSION effectively becomes an indicator of the protocol, assuming they are different. However, this is the opposite to your idea of keeping them in sync.
Since there would be no ELP registered for COMPAT_VERSION_IV, the packet would be discarded by the dispatcher. However, COMPACT_VERSION_V would register an ELP function and the dispatcher would use it.
Making the dispatcher aware of these two dimensions, (MSG_Type, Version), puts all the checking in one place and makes the individual message handlers simpler.
Anyway, just an idea...
Andrew
On Friday, April 06, 2012 10:17:29 Andrew Lunn wrote:
Currently, that is not planned. We hoped to keep the compat numbers in sync across the various protocols. Otherwise we all could end up in compat hell.
Can they be kept in sync? I would assume that IV is becoming more and more stable, with more effort going into V. So IV is less probable to need an COMPAT increment than V. The three month kernel cycle helps with the sync, but it would be a PITA to have to upgrade an entire IV net because V have forced a COMPAT increment, but IV has not changed and is compatible.
If you check our compat number history[1] you will see that the compat number changes when features are added (tt rewrite, gateway flags, unicast fragmentation, etc). These features are the same across protocols.
Another motivation to not further grow the compat number world is backward compatibility. Larger mesh installations will need to upgrade the mesh step by step instead of updating everything at once. As a result we must switch towards smoother compatibility breaks in the future otherwise upgrading will become a real pain. We have created a wiki page [2] to collect ideas for better backward compatibility.
The COMPAT_VERSION effectively becomes an indicator of the protocol, assuming they are different. However, this is the opposite to your idea of keeping them in sync.
Since there would be no ELP registered for COMPAT_VERSION_IV, the packet would be discarded by the dispatcher. However, COMPACT_VERSION_V would register an ELP function and the dispatcher would use it.
Making the dispatcher aware of these two dimensions, (MSG_Type, Version), puts all the checking in one place and makes the individual message handlers simpler.
The dispatcher has to work on a per interface basis to make this work. It would need to do the same check we currently have, to verify that a given interface wants to have packets from this or that protocol.
Regards, Marek
[1] http://www.open-mesh.org/wiki/batman-adv/Compatversion [2] http://www.open-mesh.org/wiki/batman-adv/Packet-types
On Friday, March 23, 2012 23:22:33 Andrew Lunn wrote:
I've not looked at the code, but i assume this can happen because there is not a per algorithm receive handler? Maybe it makes sense to have a receive handler in algo structure, which can handle per algorithm receive functions? The common PDUs can be handled first and then a call into the algo receive function made to dispatch algo specific PDUs.
Each algorithm registers its own packet types which end up in the protocol specific receive function. Nevertheless, we might receive a B.A.T.M.A.N. V packet on an interface not running B.A.T.M.A.N. V.
Regards, Marek
From: Linus Luessing linus.luessing@web.de
Lists all neighbours and their tq/rq values detected and measured by the Echo Location Protocol (ELP).
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 --- bat_debugfs.c | 16 +++++++++++++ bat_v_elp.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 83 insertions(+), 0 deletions(-)
diff --git a/bat_debugfs.c b/bat_debugfs.c index 3b588f8..5365554 100644 --- a/bat_debugfs.c +++ b/bat_debugfs.c @@ -227,6 +227,16 @@ static int bat_algorithms_open(struct inode *inode, struct file *file) return single_open(file, bat_algo_seq_print_text, NULL); }
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V +int bat_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, bat_v_elp_seq_print_text, net_dev); +} +#endif + static int originators_open(struct inode *inode, struct file *file) { struct net_device *net_dev = (struct net_device *)inode->i_private; @@ -283,6 +293,9 @@ struct bat_debuginfo bat_debuginfo_##_name = { \ };
static BAT_DEBUGINFO(routing_algos, S_IRUGO, bat_algorithms_open); +#ifdef CONFIG_BATMAN_ADV_BATMAN_V +static BAT_DEBUGINFO(neighbors, S_IRUGO, neighbors_open); +#endif static BAT_DEBUGINFO(originators, S_IRUGO, originators_open); static BAT_DEBUGINFO(gateways, S_IRUGO, gateways_open); static BAT_DEBUGINFO(transtable_global, S_IRUGO, transtable_global_open); @@ -293,6 +306,9 @@ static BAT_DEBUGINFO(transtable_local, S_IRUGO, transtable_local_open); static BAT_DEBUGINFO(vis_data, S_IRUGO, vis_data_open);
static struct bat_debuginfo *mesh_debuginfos[] = { +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + &bat_debuginfo_neighbors, +#endif &bat_debuginfo_originators, &bat_debuginfo_gateways, &bat_debuginfo_transtable_global, diff --git a/bat_v_elp.c b/bat_v_elp.c index e252c04..9232f28 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -394,6 +394,73 @@ out: return NET_RX_SUCCESS; }
+static void bat_v_elp_seq_print_neigh(struct seq_file *seq, + struct hard_iface *hard_iface, + struct neigh_node *neigh_node) +{ + int last_secs, last_msecs; + + last_secs = jiffies_to_msecs(jiffies - neigh_node->last_seen) / 1000; + last_msecs = jiffies_to_msecs(jiffies - neigh_node->last_seen) % 1000; + + seq_printf(seq, "%pM %4i.%03is (%3i,%3i) [%10s]\n", + neigh_node->addr, last_secs, last_msecs, neigh_node->tq, + neigh_node->rq, hard_iface->net_dev->name); +} + +int bat_v_elp_seq_print_text(struct seq_file *seq, void *offset) +{ + struct net_device *net_dev = (struct net_device *)seq->private; + struct bat_priv *bat_priv = netdev_priv(net_dev); + struct hard_iface *hard_iface, *primary_if; + struct neigh_node *neigh_node; + struct hlist_node *node; + int ret = 0, batman_count = 0; + + primary_if = primary_if_get_selected(bat_priv); + + if (!primary_if) { + ret = seq_printf(seq, "BATMAN mesh %s disabled - " + "please specify interfaces to enable it\n", + net_dev->name); + goto out; + } + + if (primary_if->if_status != IF_ACTIVE) { + ret = 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", + SOURCE_VERSION, primary_if->net_dev->name, + primary_if->net_dev->dev_addr, net_dev->name); + seq_printf(seq, " %-15s %s (%s/%i) [%10s]\n", + "Neighbor", "last-seen", "#TQ,#RQ", TQ_MAX_VALUE, "IF"); + + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface, &hardif_list, list) { + if (hard_iface->soft_iface != net_dev) + continue; + + hlist_for_each_entry_rcu(neigh_node, node, + &hard_iface->neigh_list, list) { + bat_v_elp_seq_print_neigh(seq, hard_iface, neigh_node); + batman_count++; + } + } + rcu_read_unlock(); + + if (batman_count == 0) + seq_printf(seq, "No batman nodes in range ...\n"); + +out: + if (primary_if) + hardif_free_ref(primary_if); + return ret; +} + static struct bat_algo_ops batman_v __read_mostly = { .name = "BATMAN V", .bat_iface_enable = bat_v_elp_iface_enable,
From: Linus Luessing linus.luessing@web.de
This parameter can be set individually on each interface and allows the configuration of the ndp interval for the link quality measurements during runtime. Usually it is desirable to set it to a higher (= slower) value on interfaces which have a more static characteristic (e.g. wired interfaces) or very dense neighbourhoods to reduce overhead.
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 --- bat_sysfs.c | 6 ++++++ sysfs-class-net-batman-adv | 7 +++++++ 2 files changed, 13 insertions(+), 0 deletions(-)
diff --git a/bat_sysfs.c b/bat_sysfs.c index d0f8453..6195a66 100644 --- a/bat_sysfs.c +++ b/bat_sysfs.c @@ -630,10 +630,16 @@ static ssize_t show_iface_status(struct kobject *kobj, struct attribute *attr, static BAT_ATTR(mesh_iface, S_IRUGO | S_IWUSR, show_mesh_iface, store_mesh_iface); static BAT_ATTR(iface_status, S_IRUGO, show_iface_status, NULL); +#ifdef CONFIG_BATMAN_ADV_BATMAN_V +BAT_ATTR_HIF_UINT(elp_interval, S_IRUGO | S_IWUSR, 2 * JITTER, INT_MAX, NULL); +#endif
static struct bat_attribute *batman_attrs[] = { &bat_attr_mesh_iface, &bat_attr_iface_status, +#ifdef CONFIG_BATMAN_ADV_BATMAN_V + &bat_attr_elp_interval, +#endif NULL, };
diff --git a/sysfs-class-net-batman-adv b/sysfs-class-net-batman-adv index 38dd762..954ab1f 100644 --- a/sysfs-class-net-batman-adv +++ b/sysfs-class-net-batman-adv @@ -12,3 +12,10 @@ Date: May 2010 Contact: Marek Lindner lindner_marek@yahoo.de Description: Indicates the status of <iface> as it is seen by batman. + +What: /sys/class/net/<mesh_iface>/batman-adv/elp_interval +Date: Mar 2012 +Contact: Linus Lüssing linus.luessing@web.de +Description: + Defines the interval in milliseconds in which batman + sends its probing packets for link quality measurements. \ No newline at end of file
From: Linus Luessing linus.luessing@web.de
With the current setting of no minimum ELP packet length, BATMAN very often choses too short paths. These paths are often only usable for small packets, but not for e.g. larger TCP downloads.
Therefore this commit introduces a minimum ELP packet length. If the ELP packet size is smaller than the specified minimum size the packet will be padded with zeroes up to this specified size.
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 --- bat_sysfs.c | 2 ++ bat_v_elp.c | 9 ++++++++- hard-interface.c | 1 + sysfs-class-net-batman-adv | 8 +++++++- types.h | 1 + 5 files changed, 19 insertions(+), 2 deletions(-)
diff --git a/bat_sysfs.c b/bat_sysfs.c index 6195a66..69df249 100644 --- a/bat_sysfs.c +++ b/bat_sysfs.c @@ -632,6 +632,7 @@ static BAT_ATTR(mesh_iface, S_IRUGO | S_IWUSR, static BAT_ATTR(iface_status, S_IRUGO, show_iface_status, NULL); #ifdef CONFIG_BATMAN_ADV_BATMAN_V BAT_ATTR_HIF_UINT(elp_interval, S_IRUGO | S_IWUSR, 2 * JITTER, INT_MAX, NULL); +BAT_ATTR_HIF_UINT(elp_min_len, S_IRUGO | S_IWUSR, 0, ETH_DATA_LEN, NULL); #endif
static struct bat_attribute *batman_attrs[] = { @@ -639,6 +640,7 @@ static struct bat_attribute *batman_attrs[] = { &bat_attr_iface_status, #ifdef CONFIG_BATMAN_ADV_BATMAN_V &bat_attr_elp_interval, + &bat_attr_elp_min_len, #endif NULL, }; diff --git a/bat_v_elp.c b/bat_v_elp.c index 9232f28..1bde84e 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -108,7 +108,7 @@ static void bat_v_elp_send_outstanding(struct work_struct *work) struct neigh_node *neigh_node; struct hlist_node *node; struct sk_buff *skb; - unsigned int max_len; + unsigned int max_len, min_len;
hard_iface = container_of(work, struct hard_iface, elp_wq.work); bat_priv = netdev_priv(hard_iface->soft_iface); @@ -126,6 +126,8 @@ static void bat_v_elp_send_outstanding(struct work_struct *work) goto restart_timer;
max_len = min_t(unsigned int, ETH_DATA_LEN, hard_iface->net_dev->mtu); + min_len = min_t(unsigned int, atomic_read(&hard_iface->elp_min_len), + max_len);
skb = skb_copy(hard_iface->elp_skb, GFP_ATOMIC); if (!skb) @@ -159,6 +161,11 @@ static void bat_v_elp_send_outstanding(struct work_struct *work) } rcu_read_unlock();
+ if (skb->len < min_len) { + memset(elp_neigh_entry, 0, min_len - skb->len); + skb_put(skb, min_len - skb->len); + } + bat_dbg(DBG_BATMAN, bat_priv, "Sending elp packet on interface %s, seqno %d\n", hard_iface->net_dev->name, atomic_read(&hard_iface->elp_seqno)); diff --git a/hard-interface.c b/hard-interface.c index e53e143..68cd564 100644 --- a/hard-interface.c +++ b/hard-interface.c @@ -452,6 +452,7 @@ static struct hard_iface *hardif_add_interface(struct net_device *net_dev)
#ifdef CONFIG_BATMAN_ADV_BATMAN_V atomic_set(&hard_iface->elp_interval, 500); + atomic_set(&hard_iface->elp_min_len, 300); atomic_set(&hard_iface->elp_seqno, 1); hard_iface->elp_skb = NULL; #endif /* CONFIG_BATMAN_ADV_BATMAN_V */ diff --git a/sysfs-class-net-batman-adv b/sysfs-class-net-batman-adv index 954ab1f..ddaa273 100644 --- a/sysfs-class-net-batman-adv +++ b/sysfs-class-net-batman-adv @@ -18,4 +18,10 @@ Date: Mar 2012 Contact: Linus Lüssing linus.luessing@web.de Description: Defines the interval in milliseconds in which batman - sends its probing packets for link quality measurements. \ No newline at end of file + sends its probing packets for link quality measurements. + +What: /sys/class/net/<mesh_iface>/batman-adv/elp_min_len +Date: Mar 2012 +Contact: Linus Lüssing linus.luessing@web.de +Description: + Defines the minimum ELP packet size. diff --git a/types.h b/types.h index abe27dd..f4164ea 100644 --- a/types.h +++ b/types.h @@ -60,6 +60,7 @@ struct hard_iface { struct rcu_head rcu; #ifdef CONFIG_BATMAN_ADV_BATMAN_V atomic_t elp_interval; + atomic_t elp_min_len; atomic_t elp_seqno; struct hlist_head neigh_list; spinlock_t neigh_list_lock;
- if (skb->len < min_len) {
memset(elp_neigh_entry, 0, min_len - skb->len);skb_put(skb, min_len - skb->len);- }
Hi Marek
I don't know the skbuf code too well, maybe you know it better than me.
Is this memset needed? The skb is a copy of the template ELP packet created then the soft interface is created. So if the contents of the template is set to 0, should we be able to skip this zeroing here?
Thanks Andrew
On Saturday, March 24, 2012 22:39:45 Andrew Lunn wrote:
- if (skb->len < min_len) {
memset(elp_neigh_entry, 0, min_len - skb->len);skb_put(skb, min_len - skb->len);- }
I don't know the skbuf code too well, maybe you know it better than me.
Is this memset needed? The skb is a copy of the template ELP packet created then the soft interface is created. So if the contents of the template is set to 0, should we be able to skip this zeroing here?
skb_copy() does not initialize the skb with zeros as far as I can tell. bat_v_elp_iface_enable() only writes zeros into the ELP header (BATMAN_ELP_HLEN), so zeroing the rest of the skb seems correct. We could zero the entire skb in bat_v_elp_iface_enable() to save the memset.
Regards, Marek
+static int bat_v_elp_iface_enable(struct hard_iface *hard_iface) +{
- struct batman_elp_packet *elp_packet;
- unsigned long random_seqno;
...
- /* randomize initial seqno to avoid collision */
- get_random_bytes(&random_seqno, sizeof(unsigned long));
- atomic_set(&hard_iface->elp_seqno, (uint32_t)random_seqno);
Hi Marek
Why not just make random_seqno a uint32_t and avoid the cast?
Andrew
--- a/packet.h +++ b/packet.h @@ -33,7 +33,8 @@ enum bat_packettype { BAT_UNICAST_FRAG = 0x06, BAT_TT_QUERY = 0x07, BAT_ROAM_ADV = 0x08,
- BAT_UNICAST_4ADDR = 0x09
- BAT_UNICAST_4ADDR = 0x09,
- BAT_V_ELP = 0x10
};
Hi Marek
I guess you are not on the ARM linux kernel list. A couple of months ago, Rusty had a rant about the last entry in such structures should always have a , even though its optional. As part of the ARM cleanup work he had to append a new entry to many board files, and found it very error prone. Sometime you forget to add the , to the line before, and then the compiler spits out a compile error. So since then i've got into the habit of always having a , on the last entry.
Andrew
On Friday, March 23, 2012 08:50:44 Andrew Lunn wrote:
I guess you are not on the ARM linux kernel list. A couple of months ago, Rusty had a rant about the last entry in such structures should always have a , even though its optional. As part of the ARM cleanup work he had to append a new entry to many board files, and found it very error prone. Sometime you forget to add the , to the line before, and then the compiler spits out a compile error. So since then i've got into the habit of always having a , on the last entry.
No, I don't follow the ARM list. If we wanted the comma to be there we should change the entire module. At the moment we never put the comma after the last item.
Regards, Marek
On Fri, Mar 23, 2012 at 05:50:30AM +0800, Marek Lindner wrote:
Hi,
after numerous infrastructure changes in the past weeks ELP[1] slowly approaches the state in which it can be tested and later merged into the master branch.
Hi Marek
Great to see this work going forward.
Something that Linus and I discussed was using unicast packets as well. We didn't do anything at the time, project deadlines looming etc... It is also a while ago, so maybe i'm remembering this wrong...
The problem with broadcasting the ELP packets is that they are always sent with the most robust coding rate. So ELP gives you an idea how good the 1Mbps broadcast channel is, not how good the unicast channel the automatic rate selection algorithm is using is. I think we discussed mixing in some unicast packets in the forward direction. The ELP packets containing the reports would stay the same, and so function as node detection. But a node could also send out unicast ELP packets to its known neighbours and they would be included into the LQ.
There are obvious drawbacks. More overhead, especially in dense networks. It is also not clear if the measurements would be better. Unicast packets get a number of retries with fast ACKs, where as multicast does not. So multicast might actually give a better measure of the link at 1Mbps.
Do you know if Linus had chance to explore these ideas during his GSOC?
Thanks Andrew
Hi all,
On Fri, Mar 23, 2012 at 07:32:06AM +0100, Andrew Lunn wrote:
The problem with broadcasting the ELP packets is that they are always sent with the most robust coding rate. So ELP gives you an idea how good the 1Mbps broadcast channel is, not how good the unicast channel the automatic rate selection algorithm is using is. I think we discussed mixing in some unicast packets in the forward direction. The ELP packets containing the reports would stay the same, and so function as node detection. But a node could also send out unicast ELP packets to its known neighbours and they would be included into the LQ.
I agree with you Andrew, I didn't think about a concept yet, but adding a unicast reply or something like that would help a lot imho. (Actually is this what Babel do?)
There are obvious drawbacks. More overhead, especially in dense networks. It is also not clear if the measurements would be better.
What about having a dynamic advertisement period? Again, I don't have a concept about that, but, if I remember correctly, there is another protocol called Trickle[1] which does something similar. We could take some inspiration.
Cheers,
[1]: http://csl.stanford.edu/~pal/pubs/trickle-nsdi04.pdf
Hi Andrew,
excuse the delayed answers - the wbmv5 was rather intense. ;-)
The problem with broadcasting the ELP packets is that they are always sent with the most robust coding rate. So ELP gives you an idea how good the 1Mbps broadcast channel is, not how good the unicast channel the automatic rate selection algorithm is using is. I think we discussed mixing in some unicast packets in the forward direction. The ELP packets containing the reports would stay the same, and so function as node detection. But a node could also send out unicast ELP packets to its known neighbours and they would be included into the LQ.
There are obvious drawbacks. More overhead, especially in dense networks. It is also not clear if the measurements would be better. Unicast packets get a number of retries with fast ACKs, where as multicast does not. So multicast might actually give a better measure of the link at 1Mbps.
Do you know if Linus had chance to explore these ideas during his GSOC?
the problem is known but we did not have enough time to explore it. One idea we had in mind was sending larger ELP broadcast packets every now and then in the hope of better estimating the link quality. The feature to increase the ELP packet size is part of this patchset and would allow to test this idea.
On the other hand I think we should move towards throughput based path decisions. It tells us so much more about what we really care about. Some obstacles are waiting for us if we go down this path. Have you ever experimented with this approach ?
Regards, Marek
On Thu, Apr 05, 2012 at 11:30:06PM +0300, Marek Lindner wrote:
Hi Andrew,
excuse the delayed answers - the wbmv5 was rather intense. ;-)
I got that impression for the mailing lists...
On the other hand I think we should move towards throughput based path decisions. It tells us so much more about what we really care about. Some obstacles are waiting for us if we go down this path. Have you ever experimented with this approach ?
Not directly, but we did something in SPAWN which might be relevant.
SPAWN is the automatic deployment of nodes to form a mesh inside a building. The use case is for firemen deploying nodes behind them to give mesh access to outside the building.
We want to know the link quality to the last two nodes in the chain as part of the decision when to deploy the next node in the chain. Due to work split between partners in the project, and other reasons, BATMAN is not involved in the deployment, it only gets involved once a node has been deployed. However, there is obvious overlap here...
The user space code monitors the link quality making use of the monitor interface of mac80211. One minor change was made in the kernel that allowed us to set the rate the packet would be sent at from user space on a packet by packet basis. So we could send probe packets at different rates and see which got received. You then have some idea of the link quality, what coding rates work. But it does not necessarily tell you too much about the link capacity, since you have no idea about other users of the air-space.
For a research project, such code is O.K. However, for something going into mainline, i doubt it would be accepted without strong arguments about why the existing rate control algorithm cannot be used. One difference is active vs passive. Minstral, as far as i know, makes use of existing data packets to determine the best coding rate. What the project built used its own packets. Thus it was faster to react in a changing environment when there was little traffic, which is the exact conditions during deployment.
There is a continuum here. What BATMAN has, and probably also OLSR, Babel, etc, is:
The quality of packets sent using broadcast at 1Mbps.
Using the idea above, probing using different rates we get:
The quality of packets sent using broadcast at X Mbps.
We can build a metric based on (TQ, X), picking X such that TQ is above some threshold.
If we can get reliable information out of minstral, we get:
X Mbps used for sending unicast packets in the recent past.
but this is a big change. We have lost TQ, but gained unicast to the specific originator we want the metric for. We no longer need to send probe packets, so have less overhead, but depend on there being some traffic in order that minstral can do its thing.
If we send unicast probe packets, and combine it with minstral:
The quality of packets send using unicast at X Mbps.
We have no choice on X, Minstral decides it. This is in fact good, since the real data also get X. We have a metric based on (TQ, X). How we actually determine X is interesting. TQ is a moving window average. Can we do the same for X? Minstral will already be doing some averaging, so maybe just use the latest value?
So far, we have no idea about available capacity of the link:
Determine X from Minstral. Send a burst of packets forcing them to be sent at rate X and without retries. Time how long it takes to send the packets. Compare this with the theoretical time needed, assuming no congestion, to calculate a congestion factor C.
You now can build a metric based on (TQ, X, C). But you have more overhead, because you need a burst of unicast packets, and a lot more complexity, but you have an idea of the free capacity of the link.
Andrew
but this is a big change. We have lost TQ, but gained unicast to the specific originator we want the metric for. We no longer need to send probe packets, so have less overhead, but depend on there being some traffic in order that minstral can do its thing.
If we send unicast probe packets, and combine it with minstral:
The quality of packets send using unicast at X Mbps.
We have no choice on X, Minstral decides it. This is in fact good, since the real data also get X. We have a metric based on (TQ, X). How we actually determine X is interesting. TQ is a moving window average. Can we do the same for X? Minstral will already be doing some averaging, so maybe just use the latest value?
So far, we have no idea about available capacity of the link:
Determine X from Minstral. Send a burst of packets forcing them to be sent at rate X and without retries. Time how long it takes to send the packets. Compare this with the theoretical time needed, assuming no congestion, to calculate a congestion factor C.
You now can build a metric based on (TQ, X, C). But you have more overhead, because you need a burst of unicast packets, and a lot more complexity, but you have an idea of the free capacity of the link.
Andrew
disclaimer: I am an end user, not a dev. I run a wISP (no mesh right now, ringed). Also, this is an evolved version of other ideas I posted here.
So here is my thought. How can you possibly test a wireless link for quality and capacity without sending enough data to stress the link? I do a lot of statistical work on historical product movement and sales, so I am trying to apply some lessons learned there to this problem. The only way to know capacity is to measure it. You cannot measure nothing, that is 'null', and generating traffic to measure decreases capacity/increases overhead.
My train of thought here says that you must use historical data and statistics. For this period of time x (5 seconds?), interface y transfered the aggregate amount of data z and latency to the next node in the path was L. later, x and y are unchanged but z is higher and L spikes. later x and y are unchanged but z in low and L is similar to the first entry. Keep these high water marks around and lower them when the history shows them to be invalid.
From this we can statistically say that interface y is able to
transfer z before L spikes. This is theoretical capacity of the connection. obviously, this is over wireless links so these are dynamic numbers that must be adjusted within some timeframe to changing conditions.
I find that most wireless links maintain good latency until they reach a breaking point and then the latency collapses. it hits a wall.
In the wISP world, I pre-test links and configure the radios modulation to the highest stable value. The link might negotiate at MCS15 but collapses at anything over MCS13. I do not rely on auto-adjustments here. The phenomenon of fresnel zone echo can make a link look great until data is transfered, then the echos from fresnel zone infractions destroys the link. The only way to know what is on the link is to push data across it. When I do this test, I can negatively effect other clients on the radio. This is a necessary evil for me and my tests are brief and infrequent.
If batman-adv is able to take these sort of measurements, or is able to read the results of a helper application that does the math, then it stands to reason that these numbers could be read by a helper application and the maximum modulation of a radio could be set with userspace utils (like iw) to fit the calculation to further stabilize the link. You can nudge the values up periodically to test with. If a link is MCS2 per the calculations, nudge it up to MCS3 and let the algorythm do its magic. If it still thinks that 19.5Mb is optimal we can bring the mod back down to MCS2 (via helper app), if it shows as good we will leave it at MCS3 for a while then nudge it up to MCS4. Never jump up from MCS2 to 4 because the link might completely collapse. rinse, repeat.
disclaimer: I am an end user, not a dev. I run a wISP (no mesh right now, ringed). Also, this is an evolved version of other ideas I posted here.
Hi Dan
Are you talking about point to point links using highly directional antennas, or a bunch of omni directional systems all on the same channel interfering with each other?
I've not yet looked at the details of what you said, but i get the feeling you are thinking about the first? Is that right?
Andrew
On Fri, Apr 6, 2012 at 11:19 AM, Andrew Lunn andrew@lunn.ch wrote:
disclaimer: I am an end user, not a dev. I run a wISP (no mesh right now, ringed). Also, this is an evolved version of other ideas I posted here.
Hi Dan
Are you talking about point to point links using highly directional antennas, or a bunch of omni directional systems all on the same channel interfering with each other?
I've not yet looked at the details of what you said, but i get the feeling you are thinking about the first? Is that right?
Andrew
Andrew, ideally all link types. If you are going to select path based on both TQ AND capacity, or you are going to adjust TQ based on the current criteria as well as capacity, all links matter right?
Highly directional p2p links are usually much more predictable than the AdHoc cloud, so I would say the local AdHoc cloud is the target. I have been looking at how to get the throughput on adhoc clouds but it seems that most wireless adapters 'monitor' mode is exclusive, it would take the link down to monitor the connection. In adhoc, the local nodes throughput isn't so important, because two other clients might be saturating the airwaves. Need to listen to all traffic on the waves to see capacity.
If it was easy, someone else would have already done it right ;)
cat /sys/kernel/debug/batman_adv/routing_algos Available routing algorithms: BATMAN IV BATMAN V
To activate B.A.T.M.A.N. V (ELP) you should run the following command *before* adding any interface via batctl:
echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo
Hi Marek
How about BATMAN_V and BATMAN_IV, so avoiding the need for "" or \ escaping of the space?
Thanks Andrew
On Fri, Mar 23, 2012 at 07:34:18AM +0100, Andrew Lunn wrote:
cat /sys/kernel/debug/batman_adv/routing_algos Available routing algorithms: BATMAN IV BATMAN V
To activate B.A.T.M.A.N. V (ELP) you should run the following command *before* adding any interface via batctl:
echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo
Hi Marek
How about BATMAN_V and BATMAN_IV, so avoiding the need for "" or \ escaping of the space?
I agree :) Spaces are baaaad (and ugly :P (and error prone))! I already imagine a number of people trying to change protocol without using quotes.
Cheers,
p.s. Marek thank you very much for your work
On Friday, March 23, 2012 08:34:18 Andrew Lunn wrote:
cat /sys/kernel/debug/batman_adv/routing_algos Available routing algorithms: BATMAN IV BATMAN V
To activate B.A.T.M.A.N. V (ELP) you should run the following command *before* adding any interface via batctl:
echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo
How about BATMAN_V and BATMAN_IV, so avoiding the need for "" or \ escaping of the space?
Sure, why not.
Regards, Marek
b.a.t.m.a.n@lists.open-mesh.org
-
Andrew Lunn -
Antonio Quartulli -
dan -
Marek Lindner