Adds a sha512 hash as a TVLV to an ELP packet. Hash is the "sum" of all neighbors (ordered alphabetically, concatenated, binary) a node sees on a specific interface.

Furthermore, the best and worst TX metric of all these neighbors on an interface are added to the TVLV.

Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue

---

Note: This patch throws two checkpatch warnings which are faulty, though.

Changes in v3: * ~((u32)0) -> U32_MAX (thanks Sven!) * avoid one-liner multi variable assignments (thanks Sven!) * avoid redundant set+memset -> only memset over nhh_data->neigh_hash (thanks Sven!) * set conservative hard_iface->max_throughput init value * do not attach NHH TVLV on uncertain/initialization value of hard_iface->max_throughput either * fix elp packet backwards compatibility (thanks Sven!) -> keep parsing elp packets without new tvlv field * remove unncessary linux/sha.h include (thanks Sven!) * remove linux/string.h addition in originator.h, memcmp was introduced in the previous patch already

Changes in v2: * Moved sorted storing of hardif neighbors to a separate patch * Kconfig: switched "depends on CRYPTO_SHA512" to "select CRYPTO_SHA512" * compat: for SHASH_DESC_ON_STACK() macro * kerneldoc: added "struct" prefix in kerneldoc of batadv_tvlv_nhh_data * added includes: - linux/string.h in bat_v.c - linux/{printk.h,err.h} in bat_v_elp.c - linux/string.h in originator.c (thanks Sven!) --- compat-include/crypto/hash.h | 16 ++++ net/batman-adv/Kconfig | 1 + net/batman-adv/bat_v.c | 28 ++++++- net/batman-adv/bat_v.h | 5 ++ net/batman-adv/bat_v_elp.c | 186 ++++++++++++++++++++++++++++++++++++++++++- net/batman-adv/bat_v_elp.h | 2 + net/batman-adv/log.c | 4 +- net/batman-adv/main.c | 1 + net/batman-adv/packet.h | 26 ++++++ net/batman-adv/types.h | 8 ++ 10 files changed, 271 insertions(+), 6 deletions(-) create mode 100644 compat-include/crypto/hash.h

diff --git a/compat-include/crypto/hash.h b/compat-include/crypto/hash.h new file mode 100644 index 0000000..2dd72ea --- /dev/null +++ b/compat-include/crypto/hash.h @@ -0,0 +1,16 @@ +#ifndef _NET_BATMAN_ADV_COMPAT_CRYPTO_HASH_H_ +#define _NET_BATMAN_ADV_COMPAT_CRYPTO_HASH_H_ + +#include <linux/version.h> +#include_next <crypto/hash.h> + +#if LINUX_VERSION_CODE < KERNEL_VERSION(3, 18, 0) + +#define SHASH_DESC_ON_STACK(shash, ctx) \ + char __##shash##_desc[sizeof(struct shash_desc) + \ + crypto_shash_descsize(ctx)] CRYPTO_MINALIGN_ATTR; \ + struct shash_desc *shash = (struct shash_desc *)__##shash##_desc + +#endif /* < KERNEL_VERSION(3, 18, 0) */ + +#endif /* _NET_BATMAN_ADV_COMPAT_CRYPTO_HASH_H_ */ diff --git a/net/batman-adv/Kconfig b/net/batman-adv/Kconfig index b73b96a..54980d8 100644 --- a/net/batman-adv/Kconfig +++ b/net/batman-adv/Kconfig @@ -18,6 +18,7 @@ config BATMAN_ADV config BATMAN_ADV_BATMAN_V bool "B.A.T.M.A.N. V protocol (experimental)" depends on BATMAN_ADV && !(CFG80211=m && BATMAN_ADV=y) + select CRYPTO_SHA512 default n help This option enables the B.A.T.M.A.N. V protocol, the successor diff --git a/net/batman-adv/bat_v.c b/net/batman-adv/bat_v.c index 0acd081..992e428 100644 --- a/net/batman-adv/bat_v.c +++ b/net/batman-adv/bat_v.c @@ -33,6 +33,7 @@ #include <linux/rcupdate.h> #include <linux/seq_file.h> #include <linux/stddef.h> +#include <linux/string.h> #include <linux/types.h> #include <linux/workqueue.h> #include <net/genetlink.h> @@ -1070,11 +1071,17 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = { */ void batadv_v_hardif_init(struct batadv_hard_iface *hard_iface) { + struct batadv_hard_iface_bat_v *bat_v = &hard_iface->bat_v; + /* enable link throughput auto-detection by setting the throughput * override to zero */ - atomic_set(&hard_iface->bat_v.throughput_override, 0); - atomic_set(&hard_iface->bat_v.elp_interval, 500); + atomic_set(&bat_v->throughput_override, 0); + atomic_set(&bat_v->elp_interval, 500); + + bat_v->min_throughput = 0; + bat_v->max_throughput = U32_MAX; + memset(bat_v->neigh_hash, 0, sizeof(bat_v->neigh_hash)); }

/** @@ -1108,6 +1115,14 @@ void batadv_v_mesh_free(struct batadv_priv *bat_priv) }

/** + * batadv_v_free - free the B.A.T.M.A.N. V global, mesh independent resources + */ +void batadv_v_free(void) +{ + batadv_v_elp_free(); +} + +/** * batadv_v_init - B.A.T.M.A.N. V initialization function * * Description: Takes care of initializing all the subcomponents. @@ -1119,11 +1134,15 @@ int __init batadv_v_init(void) { int ret;

+ ret = batadv_v_elp_init(); + if (ret < 0) + return ret; + /* B.A.T.M.A.N. V echo location protocol packet */ ret = batadv_recv_handler_register(BATADV_ELP, batadv_v_elp_packet_recv); if (ret < 0) - return ret; + goto elp_free;

ret = batadv_recv_handler_register(BATADV_OGM2, batadv_v_ogm_packet_recv); @@ -1136,6 +1155,9 @@ int __init batadv_v_init(void)

return ret;

+elp_free: + batadv_v_elp_free(); + ogm_unregister: batadv_recv_handler_unregister(BATADV_OGM2);

diff --git a/net/batman-adv/bat_v.h b/net/batman-adv/bat_v.h index dd7c4b6..9782ba1 100644 --- a/net/batman-adv/bat_v.h +++ b/net/batman-adv/bat_v.h @@ -23,6 +23,7 @@ #ifdef CONFIG_BATMAN_ADV_BATMAN_V

int batadv_v_init(void); +void batadv_v_free(void); void batadv_v_hardif_init(struct batadv_hard_iface *hardif); int batadv_v_mesh_init(struct batadv_priv *bat_priv); void batadv_v_mesh_free(struct batadv_priv *bat_priv); @@ -34,6 +35,10 @@ static inline int batadv_v_init(void) return 0; }

+static inline void batadv_v_free(void) +{ +} + static inline void batadv_v_hardif_init(struct batadv_hard_iface *hardif) { } diff --git a/net/batman-adv/bat_v_elp.c b/net/batman-adv/bat_v_elp.c index b90c990..df7bc64 100644 --- a/net/batman-adv/bat_v_elp.c +++ b/net/batman-adv/bat_v_elp.c @@ -18,8 +18,10 @@ #include "bat_v_elp.h" #include "main.h"

+#include <crypto/hash.h> #include <linux/atomic.h> #include <linux/byteorder/generic.h> +#include <linux/err.h> #include <linux/errno.h> #include <linux/etherdevice.h> #include <linux/ethtool.h> @@ -29,6 +31,7 @@ #include <linux/kernel.h> #include <linux/kref.h> #include <linux/netdevice.h> +#include <linux/printk.h> #include <linux/random.h> #include <linux/rculist.h> #include <linux/rcupdate.h> @@ -49,6 +52,8 @@ #include "routing.h" #include "send.h"

+static struct crypto_shash *tfm; + /** * batadv_v_elp_start_timer - restart timer for ELP periodic work * @hard_iface: the interface for which the timer has to be reset @@ -65,6 +70,136 @@ static void batadv_v_elp_start_timer(struct batadv_hard_iface *hard_iface) }

/** + * batadv_v_elp_update_neigh_hash - updates neighborhood hash related data + * @hard_iface: interface which the data has to be prepared for + * + * Firstly, this function updates the neighborhood hash of a hard interface. + * That is it resummarizes the present neighborhood into one compact hash + * representation. + * + * Secondly, minimum and maximum throughput values within this neighorhood are + * updated. + */ +static void batadv_v_elp_update_neigh_hash(struct batadv_hard_iface *hard_iface) +{ + struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); + struct batadv_hardif_neigh_node *hardif_neigh = NULL; + struct ewma_throughput *ewma_throughput; + u8 *own_addr = hard_iface->net_dev->dev_addr; + u32 min_throughput = U32_MAX; + u32 max_throughput = 0; + u32 throughput; + int ret; + + SHASH_DESC_ON_STACK(shash, tfm); + + shash->flags = 0; + shash->tfm = tfm; + + ret = crypto_shash_init(shash); + if (ret) + goto err; + + rcu_read_lock(); + hlist_for_each_entry_rcu(hardif_neigh, + &hard_iface->neigh_list, list) { + /* insert own address at the right spot */ + if (own_addr && (memcmp(own_addr, hardif_neigh->addr, + ETH_ALEN) < 0)) { + ret = crypto_shash_update(shash, own_addr, ETH_ALEN); + if (ret) { + rcu_read_unlock(); + goto err; + } + + own_addr = NULL; + } + + ret = crypto_shash_update(shash, hardif_neigh->addr, ETH_ALEN); + if (ret) { + rcu_read_unlock(); + goto err; + } + + ewma_throughput = &hardif_neigh->bat_v.throughput; + throughput = ewma_throughput_read(ewma_throughput); + + if (throughput < min_throughput) + min_throughput = throughput; + + if (throughput > max_throughput) + max_throughput = throughput; + } + rcu_read_unlock(); + + if (own_addr) { + ret = crypto_shash_update(shash, own_addr, ETH_ALEN); + if (ret) + goto err; + } + + ret = crypto_shash_final(shash, hard_iface->bat_v.neigh_hash); + if (ret) + goto err; + + hard_iface->bat_v.min_throughput = min_throughput; + hard_iface->bat_v.max_throughput = max_throughput; + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Updated neighbor hash on interface %s: %*phN, min_through: %u kbit/s, max_through: %u kbit/s\n", + hard_iface->net_dev->name, + (int)sizeof(hard_iface->bat_v.neigh_hash), + hard_iface->bat_v.neigh_hash, + hard_iface->bat_v.min_throughput * 100, + hard_iface->bat_v.max_throughput * 100); + + return; + +err: + memset(hard_iface->bat_v.neigh_hash, 0, + sizeof(hard_iface->bat_v.neigh_hash)); + hard_iface->bat_v.min_throughput = 0; + hard_iface->bat_v.max_throughput = U32_MAX; + + pr_warn_once("An error occurred while calculating neighbor hash for %s\n", + hard_iface->net_dev->name); +} + +/** + * batadv_v_elp_update_neigh_hash_tvlv - updates a neighborhood hash tvlv + * @hard_iface: interface which the tvlv is updated for + * @skb: the to be transmitted ELP packet containing the neighborhood tvlv + * + * Prepares the neighborhood hash tvlv of an ELP packet by updating its + * hash as well as minimum and maximum throughput values. + */ +static void +batadv_v_elp_update_neigh_hash_tvlv(struct batadv_hard_iface *hard_iface, + struct sk_buff *skb) +{ + struct batadv_hard_iface_bat_v *hard_iface_v = &hard_iface->bat_v; + struct batadv_elp_packet *elp_packet; + struct batadv_tvlv_hdr *tvlv_hdr; + struct batadv_tvlv_nhh_data *nhh_data; + + elp_packet = (struct batadv_elp_packet *)skb_network_header(skb); + tvlv_hdr = (struct batadv_tvlv_hdr *)(elp_packet + 1); + nhh_data = (struct batadv_tvlv_nhh_data *)(tvlv_hdr + 1); + + /* no rumours: do not announce uncertain/initialization values */ + if (hard_iface_v->min_throughput == 0 || + hard_iface_v->max_throughput == U32_MAX) { + elp_packet->tvlv_len = 0; + skb_trim(skb, skb->len - sizeof(*tvlv_hdr) - sizeof(*nhh_data)); + } else { + nhh_data->min_throughput = htonl(hard_iface_v->min_throughput); + nhh_data->max_throughput = htonl(hard_iface_v->max_throughput); + memcpy(nhh_data->neigh_hash, hard_iface_v->neigh_hash, + sizeof(hard_iface_v->neigh_hash)); + } +} + +/** * batadv_v_elp_get_throughput - get the throughput towards a neighbour * @neigh: the neighbour for which the throughput has to be obtained * @@ -274,6 +409,9 @@ static void batadv_v_elp_periodic_work(struct work_struct *work) elp_interval = atomic_read(&hard_iface->bat_v.elp_interval); elp_packet->elp_interval = htonl(elp_interval);

+ batadv_v_elp_update_neigh_hash(hard_iface); + batadv_v_elp_update_neigh_hash_tvlv(hard_iface, skb); + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "Sending broadcast ELP packet on interface %s, seqno %u\n", hard_iface->net_dev->name, @@ -329,23 +467,43 @@ out: int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface) { struct batadv_elp_packet *elp_packet; + struct batadv_tvlv_hdr *tvlv_hdr; + struct batadv_tvlv_nhh_data *nhh_data; unsigned char *elp_buff; u32 random_seqno; size_t size; int res = -ENOMEM;

size = ETH_HLEN + NET_IP_ALIGN + BATADV_ELP_HLEN; + size += sizeof(*nhh_data) + sizeof(*tvlv_hdr); + 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); + skb_reset_network_header(hard_iface->bat_v.elp_skb); + elp_buff = skb_put(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->tvlv_len = htons(sizeof(*nhh_data) + sizeof(*tvlv_hdr)); + + elp_buff = skb_put(hard_iface->bat_v.elp_skb, sizeof(*tvlv_hdr)); + tvlv_hdr = (struct batadv_tvlv_hdr *)elp_buff; + tvlv_hdr->type = BATADV_TVLV_NHH; + tvlv_hdr->version = 1; + tvlv_hdr->len = htons(sizeof(*nhh_data)); + + size = sizeof(*nhh_data); + elp_buff = skb_put(hard_iface->bat_v.elp_skb, size); + nhh_data = (struct batadv_tvlv_nhh_data *)elp_buff; + nhh_data->min_throughput = htonl(0); + nhh_data->max_throughput = htonl(U32_MAX); + memset(nhh_data->neigh_hash, 0, size);

/* randomize initial seqno to avoid collision */ get_random_bytes(&random_seqno, sizeof(random_seqno)); @@ -497,10 +655,14 @@ int batadv_v_elp_packet_recv(struct sk_buff *skb, struct batadv_elp_packet *elp_packet; struct batadv_hard_iface *primary_if; struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb); + unsigned int min_elp_len = BATADV_ELP_HLEN; bool res; int ret = NET_RX_DROP;

- res = batadv_check_management_packet(skb, if_incoming, BATADV_ELP_HLEN); + min_elp_len -= sizeof(elp_packet->tvlv_len); + min_elp_len -= sizeof(elp_packet->reserved); + + res = batadv_check_management_packet(skb, if_incoming, min_elp_len); if (!res) goto free_skb;

@@ -538,3 +700,25 @@ free_skb:

return ret; } + +/** + * batadv_v_elp_init - initialize global ELP structures + * + * Return: A negative value on error, zero on success. + */ +int batadv_v_elp_init(void) +{ + tfm = crypto_alloc_shash("sha512", 0, 0); + if (IS_ERR(tfm)) + return PTR_ERR(tfm); + + return 0; +} + +/** + * batadv_v_elp_free - free global ELP structures + */ +void batadv_v_elp_free(void) +{ + crypto_free_shash(tfm); +} diff --git a/net/batman-adv/bat_v_elp.h b/net/batman-adv/bat_v_elp.h index 376ead2..2e73047 100644 --- a/net/batman-adv/bat_v_elp.h +++ b/net/batman-adv/bat_v_elp.h @@ -23,6 +23,8 @@ struct sk_buff; struct work_struct;

+int batadv_v_elp_init(void); +void batadv_v_elp_free(void); 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_iface_activate(struct batadv_hard_iface *primary_iface, diff --git a/net/batman-adv/log.c b/net/batman-adv/log.c index 4ef4bde..5c0337d 100644 --- a/net/batman-adv/log.c +++ b/net/batman-adv/log.c @@ -65,7 +65,7 @@ static int batadv_fdebug_log(struct batadv_priv_debug_log *debug_log, const char *fmt, ...) { va_list args; - static char debug_log_buf[256]; + static char debug_log_buf[512]; char *p;

if (!debug_log) @@ -89,7 +89,7 @@ static int batadv_fdebug_log(struct batadv_priv_debug_log *debug_log, int batadv_debug_log(struct batadv_priv *bat_priv, const char *fmt, ...) { va_list args; - char tmp_log_buf[256]; + char tmp_log_buf[512];

va_start(args, fmt); vscnprintf(tmp_log_buf, sizeof(tmp_log_buf), fmt, args); diff --git a/net/batman-adv/main.c b/net/batman-adv/main.c index 5000c54..5efe40b 100644 --- a/net/batman-adv/main.c +++ b/net/batman-adv/main.c @@ -137,6 +137,7 @@ static void __exit batadv_exit(void) rcu_barrier();

batadv_tt_cache_destroy(); + batadv_v_free(); }

int batadv_mesh_init(struct net_device *soft_iface) diff --git a/net/batman-adv/packet.h b/net/batman-adv/packet.h index 8e8a5db..4de324f 100644 --- a/net/batman-adv/packet.h +++ b/net/batman-adv/packet.h @@ -19,6 +19,7 @@ #define _NET_BATMAN_ADV_PACKET_H_

#include <asm/byteorder.h> +#include <crypto/sha.h> #include <linux/types.h>

#define batadv_tp_is_error(n) ((u8)(n) > 127 ? 1 : 0) @@ -163,6 +164,14 @@ enum batadv_tvlv_type { BATADV_TVLV_MCAST = 0x06, };

+/** + * enum batadv_tvlv_elp_type - tvlv type definitions for ELP messages + * @BATADV_TVLV_NHH: neighborhood hash + */ +enum batadv_tvlv_elp_type { + BATADV_TVLV_NHH = 0x01, +}; + #pragma pack(2) /* the destination hardware field in the ARP frame is used to * transport the claim type and the group id @@ -240,6 +249,8 @@ struct batadv_ogm2_packet { * @orig: originator mac address * @seqno: sequence number * @elp_interval: currently used ELP sending interval in ms + * @reserved: reserved bytes for alignment + * @tvlv_len: length of tvlv data following the elp header */ struct batadv_elp_packet { u8 packet_type; @@ -247,6 +258,8 @@ struct batadv_elp_packet { u8 orig[ETH_ALEN]; __be32 seqno; __be32 elp_interval; + __be16 reserved; + __be16 tvlv_len; };

#define BATADV_ELP_HLEN sizeof(struct batadv_elp_packet) @@ -618,4 +631,17 @@ struct batadv_tvlv_mcast_data { u8 reserved[3]; };

+/** + * struct batadv_tvlv_nhh_data - neighborhood hash data + * @min_throughput: worst of all TX throughputs this neighbor has to others + * @max_throughput: best of all TX throughputs this neighbor has to others + * @neigh_hash: a sha512 hash of all neighbors this neighbor sees + * (hash over the alphabetically ordered, concatenated, binary representation) + */ +struct batadv_tvlv_nhh_data { + __be32 min_throughput; + __be32 max_throughput; + u8 neigh_hash[SHA512_DIGEST_SIZE]; +}; + #endif /* _NET_BATMAN_ADV_PACKET_H_ */ diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h index 8f64a5c..000a26d 100644 --- a/net/batman-adv/types.h +++ b/net/batman-adv/types.h @@ -22,6 +22,7 @@ #error only "main.h" can be included directly #endif

+#include <crypto/sha.h> #include <linux/average.h> #include <linux/bitops.h> #include <linux/compiler.h> @@ -108,6 +109,10 @@ enum batadv_v_hard_iface_flags { * @elp_wq: workqueue used to schedule ELP transmissions * @throughput_override: throughput override to disable link auto-detection * @flags: interface specific flags + * @min_throughput: worst of all TX throughputs this neighbor has to others + * @max_throughput: best of all TX throughputs this neighbor has to others + * @neigh_hash: a sha512 hash of all neighbors this neighbor sees + * (hash over the alphabetically ordered, concatenated, binary representation) */ struct batadv_hard_iface_bat_v { atomic_t elp_interval; @@ -116,6 +121,9 @@ struct batadv_hard_iface_bat_v { struct delayed_work elp_wq; atomic_t throughput_override; u8 flags; + u32 min_throughput; + u32 max_throughput; + u8 neigh_hash[SHA512_DIGEST_SIZE]; };

/**

This patch aims to reduce protocol overhead for BATMAN V by avoiding rebroadcasts of OGM2 and broadcast packets in neighborhoods where every neighbor "sees" another.

This is done by parsing and storing the new information provided by the ELP specific neighborhood hash TVLV.

We then use this new information to detect certain scenarios where a rebroadcast of OGM2 and broadcast packets on the incoming interface is unncessary.

In a nutshell the detection checks whether all neighbors see each other by comparing their with a neighbors hash. If so, then a node deciding to rebroadcast will check whether either the ingress side or the egress side might be a bottleneck metric wise. In other words, whether a rebroadcast might not enhance any throughput.

Signed-off-by: Linus Lüssing linus.luessing@c0d3.blue

---

Changes in v3: * ~((u32)0) -> U32_MAX * avoid one-liner multi variable assignments * fix elp packet backwards compatibility: -> keep parsing elp packets without new tvlv field * add missing linux/bug.h include in bat_v_elp.c for WARN_ON() * remove tvlv (un)pack_ctx wrappers (thanks Sven!)

Changes in v2: * added kerneldoc for new @skb in batadv_v_elp_neigh_update() * added include for linux/types.h in bat_v_elp.h * removed a duplicate bat_v_ogm.h include in bat_v_ogm.c * adjusted alignment for new function in algo_iface_ops (thanks Sven!) --- net/batman-adv/bat_v.c | 40 +++++- net/batman-adv/bat_v_elp.c | 304 +++++++++++++++++++++++++++++++++++++++- net/batman-adv/bat_v_elp.h | 12 ++ net/batman-adv/bat_v_ogm.c | 18 ++- net/batman-adv/bat_v_ogm.h | 4 + net/batman-adv/hard-interface.c | 47 ++++--- net/batman-adv/hard-interface.h | 6 +- net/batman-adv/send.c | 8 +- net/batman-adv/types.h | 17 +++ 9 files changed, 421 insertions(+), 35 deletions(-)

diff --git a/net/batman-adv/bat_v.c b/net/batman-adv/bat_v.c index 992e428..764d4e1 100644 --- a/net/batman-adv/bat_v.c +++ b/net/batman-adv/bat_v.c @@ -126,6 +126,9 @@ static void batadv_v_hardif_neigh_init(struct batadv_hardif_neigh_node *hardif_neigh) { ewma_throughput_init(&hardif_neigh->bat_v.throughput); + hardif_neigh->bat_v.min_throughput = 0; + memset(hardif_neigh->bat_v.neigh_hash, 0, + sizeof(hardif_neigh->bat_v.neigh_hash)); INIT_WORK(&hardif_neigh->bat_v.metric_work, batadv_v_elp_throughput_metric_update); } @@ -172,14 +175,33 @@ batadv_v_hardif_neigh_print(struct seq_file *seq, { int last_secs, last_msecs; u32 throughput; + char nhh_avoid_ogm = '.', nhh_avoid_bcast = '.'; + bool same_hash; + + same_hash = batadv_v_elp_nhh_cmp(hardif_neigh); + + if (same_hash) { + if (batadv_v_elp_rx_ingress_bad(hardif_neigh)) + nhh_avoid_ogm = 'A'; + + if (batadv_v_elp_rx_egress_bad(hardif_neigh)) + nhh_avoid_ogm = (nhh_avoid_ogm == '.') ? 'B' : 'C'; + + if (batadv_v_elp_tx_ingress_bad(hardif_neigh)) + nhh_avoid_bcast = 'X'; + + if (batadv_v_elp_tx_egress_bad(hardif_neigh)) + nhh_avoid_bcast = (nhh_avoid_bcast == '.') ? 'Y' : 'Z'; + }

last_secs = jiffies_to_msecs(jiffies - hardif_neigh->last_seen) / 1000; last_msecs = jiffies_to_msecs(jiffies - hardif_neigh->last_seen) % 1000; throughput = ewma_throughput_read(&hardif_neigh->bat_v.throughput);

- seq_printf(seq, "%pM %4i.%03is (%9u.%1u) [%10s]\n", + seq_printf(seq, "%pM %4i.%03is (%9u.%1u) [%10s] [%c%c%c]\n", hardif_neigh->addr, last_secs, last_msecs, throughput / 10, - throughput % 10, hardif_neigh->if_incoming->net_dev->name); + throughput % 10, hardif_neigh->if_incoming->net_dev->name, + same_hash ? 'H' : '.', nhh_avoid_ogm, nhh_avoid_bcast); }

/** @@ -196,7 +218,7 @@ static void batadv_v_neigh_print(struct batadv_priv *bat_priv, int batman_count = 0;

seq_puts(seq, - " Neighbor last-seen ( throughput) [ IF]\n"); + " Neighbor last-seen ( throughput) [ IF] NHH-flags\n");

rcu_read_lock(); list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { @@ -1039,6 +1061,7 @@ static struct batadv_algo_ops batadv_batman_v __read_mostly = { }, .neigh = { .hardif_init = batadv_v_hardif_neigh_init, + .hardif_no_broadcast = batadv_v_elp_no_broadcast, .cmp = batadv_v_neigh_cmp, .is_similar_or_better = batadv_v_neigh_is_sob, #ifdef CONFIG_BATMAN_ADV_DEBUGFS @@ -1081,6 +1104,9 @@ void batadv_v_hardif_init(struct batadv_hard_iface *hard_iface)

bat_v->min_throughput = 0; bat_v->max_throughput = U32_MAX; + bat_v->min_throughput_other = 0; + bat_v->max_throughput_other = U32_MAX; + memset(bat_v->neigh_hash, 0, sizeof(bat_v->neigh_hash)); }

@@ -1095,9 +1121,15 @@ int batadv_v_mesh_init(struct batadv_priv *bat_priv) { int ret = 0;

+ ret = batadv_v_elp_mesh_init(bat_priv); + if (ret < 0) + return ret; + ret = batadv_v_ogm_init(bat_priv); - if (ret < 0) + if (ret < 0) { + batadv_v_elp_mesh_free(bat_priv); return ret; + }

/* set default throughput difference threshold to 5Mbps */ atomic_set(&bat_priv->gw.sel_class, 50); diff --git a/net/batman-adv/bat_v_elp.c b/net/batman-adv/bat_v_elp.c index df7bc64..752789f 100644 --- a/net/batman-adv/bat_v_elp.c +++ b/net/batman-adv/bat_v_elp.c @@ -20,6 +20,7 @@

#include <crypto/hash.h> #include <linux/atomic.h> +#include <linux/bug.h> #include <linux/byteorder/generic.h> #include <linux/err.h> #include <linux/errno.h> @@ -51,6 +52,7 @@ #include "packet.h" #include "routing.h" #include "send.h" +#include "tvlv.h"

static struct crypto_shash *tfm;

@@ -88,6 +90,8 @@ static void batadv_v_elp_update_neigh_hash(struct batadv_hard_iface *hard_iface) u8 *own_addr = hard_iface->net_dev->dev_addr; u32 min_throughput = U32_MAX; u32 max_throughput = 0; + u32 min_throughput_other = U32_MAX; + u32 max_throughput_other = 0; u32 throughput; int ret;

@@ -129,6 +133,16 @@ static void batadv_v_elp_update_neigh_hash(struct batadv_hard_iface *hard_iface)

if (throughput > max_throughput) max_throughput = throughput; + + throughput = hardif_neigh->bat_v.min_throughput; + + if (throughput < min_throughput_other) + min_throughput_other = throughput; + + throughput = hardif_neigh->bat_v.max_throughput; + + if (throughput > max_throughput_other) + max_throughput_other = throughput; } rcu_read_unlock();

@@ -144,14 +158,18 @@ static void batadv_v_elp_update_neigh_hash(struct batadv_hard_iface *hard_iface)

hard_iface->bat_v.min_throughput = min_throughput; hard_iface->bat_v.max_throughput = max_throughput; + hard_iface->bat_v.min_throughput_other = min_throughput_other; + hard_iface->bat_v.max_throughput_other = max_throughput_other;

batadv_dbg(BATADV_DBG_BATMAN, bat_priv, - "Updated neighbor hash on interface %s: %*phN, min_through: %u kbit/s, max_through: %u kbit/s\n", + "Updated neighbor hash on interface %s: %*phN, min_through: %u kbit/s, max_through: %u kbit/s, min_through_other: %u kbit/s, max_through_other: %u kbit/s\n", hard_iface->net_dev->name, (int)sizeof(hard_iface->bat_v.neigh_hash), hard_iface->bat_v.neigh_hash, hard_iface->bat_v.min_throughput * 100, - hard_iface->bat_v.max_throughput * 100); + hard_iface->bat_v.max_throughput * 100, + hard_iface->bat_v.min_throughput_other * 100, + hard_iface->bat_v.max_throughput_other * 100);

return;

@@ -160,6 +178,8 @@ err: sizeof(hard_iface->bat_v.neigh_hash)); hard_iface->bat_v.min_throughput = 0; hard_iface->bat_v.max_throughput = U32_MAX; + hard_iface->bat_v.min_throughput_other = 0; + hard_iface->bat_v.max_throughput_other = U32_MAX;

pr_warn_once("An error occurred while calculating neighbor hash for %s\n", hard_iface->net_dev->name); @@ -581,8 +601,27 @@ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *primary_iface) }

/** + * batadv_v_elp_get_tvlv_len - get tvlv_len of an elp packet + * @skb: the elp packet to parse + * + * Return: Length of the tvlv data of the given skb. + */ +static u16 batadv_v_elp_get_tvlv_len(struct sk_buff *skb) +{ + unsigned int tvlv_len_offset; + __be16 *tvlv_len, tvlv_len_buff; + + tvlv_len_offset = offsetof(struct batadv_elp_packet, tvlv_len); + tvlv_len = skb_header_pointer(skb, tvlv_len_offset, + sizeof(tvlv_len_buff), &tvlv_len_buff); + + return tvlv_len ? ntohs(*tvlv_len) : 0; +} + +/** * batadv_v_elp_neigh_update - update an ELP neighbour node * @bat_priv: the bat priv with all the soft interface information + * @skb: the received packet * @neigh_addr: the neighbour interface address * @if_incoming: the interface the packet was received through * @elp_packet: the received ELP packet @@ -591,6 +630,7 @@ void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *primary_iface) * ELP packet. */ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv, + struct sk_buff *skb, u8 *neigh_addr, struct batadv_hard_iface *if_incoming, struct batadv_elp_packet *elp_packet) @@ -599,6 +639,8 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv, struct batadv_neigh_node *neigh; struct batadv_orig_node *orig_neigh; struct batadv_hardif_neigh_node *hardif_neigh; + unsigned int tvlv_offset = sizeof(*elp_packet); + u16 tvlv_len = batadv_v_elp_get_tvlv_len(skb); s32 seqno_diff; s32 elp_latest_seqno;

@@ -615,6 +657,9 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv, if (!hardif_neigh) goto neigh_free;

+ batadv_tvlv_containers_process2(bat_priv, skb, BATADV_ELP, tvlv_offset, + tvlv_len, hardif_neigh); + elp_latest_seqno = hardif_neigh->bat_v.elp_latest_seqno; seqno_diff = ntohl(elp_packet->seqno) - elp_latest_seqno;

@@ -686,7 +731,7 @@ int batadv_v_elp_packet_recv(struct sk_buff *skb, if (!primary_if) goto free_skb;

- batadv_v_elp_neigh_update(bat_priv, ethhdr->h_source, if_incoming, + batadv_v_elp_neigh_update(bat_priv, skb, ethhdr->h_source, if_incoming, elp_packet);

ret = NET_RX_SUCCESS; @@ -702,6 +747,259 @@ free_skb: }

/** + * batadv_v_elp_nhh_cmp - compares a neighbor's hash with the own one + * @hardif_neigh: the hardif_neigh to compare with + * + * Checks whether the neighbor hash a neighbor advertised matches our own + * hash, the one we computed for the same interface. + * + * Return: True, if the hashes match, false otherwise. + */ +bool batadv_v_elp_nhh_cmp(struct batadv_hardif_neigh_node *hardif_neigh) +{ + return !memcmp(hardif_neigh->if_incoming->bat_v.neigh_hash, + hardif_neigh->bat_v.neigh_hash, + sizeof(hardif_neigh->bat_v.neigh_hash)); +} + +/** + * batadv_v_elp_rx_ingress_bad - check for ingress RX-metric bottlenecks + * @hardif_neigh: the hardif_neigh a packet was received from + * + * Checks whether we could potentially be a better path for packets + * coming from the given hardif_neigh to any neighbor on the same interface. + * Or whether there is some bottleneck making us unfavourable to become + * a forwarder for packets from this hardif_neigh. + * + * More specifically, this function checks whether our ingress side, that + * is the connection from us to the given hardif_neigh, is worse than the + * direct transmission any other neighbor to this hardif_neigh. + * + * Return: True if our incoming side a bottleneck, false otherwise. + */ + +bool batadv_v_elp_rx_ingress_bad(struct batadv_hardif_neigh_node *hardif_neigh) +{ + struct batadv_hard_iface *iface = hardif_neigh->if_incoming; + struct batadv_priv *bat_priv = netdev_priv(iface->soft_iface); + u32 throughput = ewma_throughput_read(&hardif_neigh->bat_v.throughput); + u32 limit = iface->bat_v.min_throughput_other; + + throughput = batadv_v_forward_penalty(bat_priv, iface, iface, + throughput); + + return throughput < limit; +} + +/** + * batadv_v_elp_rx_egress_bad - check for egress RX-metric bottlenecks + * @hardif_neigh: the hardif_neigh a packet was received from + * + * Checks whether we could potentially be a better path for packets + * coming from the given hardif_neigh to any neighbor on the same interface. + * Or whether there is some bottleneck making us unfavourable to become + * a forwarder for packets from this hardif_neigh. + * + * More specifically, this function checks whether our egress side, that is + * the connection from from any neighbor other than hardif_neigh to us, is + * worse than the direct transmission of any other neighbor to this + * hardif_neigh. + * + * Return: True if our outgoing side a bottleneck, false otherwise. + */ +bool batadv_v_elp_rx_egress_bad(struct batadv_hardif_neigh_node *hardif_neigh) +{ + struct batadv_hard_iface *iface = hardif_neigh->if_incoming; + struct batadv_priv *bat_priv = netdev_priv(iface->soft_iface); + u32 throughput = iface->bat_v.max_throughput_other; + u32 limit = iface->bat_v.min_throughput_other; + + throughput = batadv_v_forward_penalty(bat_priv, iface, iface, + throughput); + + return throughput < limit; +} + +/** + * batadv_v_elp_tx_ingress_bad - check for ingress TX-metric bottlenecks + * @hardif_neigh: the hardif_neigh a packet was received from + * + * Checks whether we could potentially be a better path for packets + * coming from the given hardif_neigh to any neighbor on the same interface. + * Or whether there is some bottleneck making us unfavourable to become + * a forwarder for packets from this hardif_neigh. + * + * More specifically, this function checks whether our ingress side, that + * is the connection from the given hardif_neigh to us, is worse than the + * direct transmission of the hardif_neigh to any other neighbor. + * + * Return: True if our incoming side a bottleneck, false otherwise. + */ +bool batadv_v_elp_tx_ingress_bad(struct batadv_hardif_neigh_node *hardif_neigh) +{ + struct batadv_hard_iface *iface = hardif_neigh->if_incoming; + struct batadv_priv *bat_priv = netdev_priv(iface->soft_iface); + u32 throughput = hardif_neigh->bat_v.max_throughput; + u32 limit = hardif_neigh->bat_v.min_throughput; + + throughput = batadv_v_forward_penalty(bat_priv, iface, iface, + throughput); + + return throughput < limit; +} + +/** + * batadv_v_elp_tx_egress_bad - check for egress TX-metric bottlenecks + * @hardif_neigh: the hardif_neigh a packet was received from + * + * Checks whether we could potentially be a better path for packets + * coming from the given hardif_neigh to any neighbor on the same interface. + * Or whether there is some bottleneck making us unfavourable to become + * a forwarder for packets from this hardif_neigh. + * + * More specifically, this function checks whether our egress side, that is + * the connection from us to any neighbor other than hardif_neigh, is + * worse than the direct transmission of the hardif_neigh to any other neighbor. + * + * Return: True if our outgoing side a bottleneck, false otherwise. + */ +bool batadv_v_elp_tx_egress_bad(struct batadv_hardif_neigh_node *hardif_neigh) +{ + struct batadv_hard_iface *iface = hardif_neigh->if_incoming; + struct batadv_priv *bat_priv = netdev_priv(iface->soft_iface); + u32 throughput = iface->bat_v.max_throughput; + u32 limit = hardif_neigh->bat_v.min_throughput; + + throughput = batadv_v_forward_penalty(bat_priv, iface, iface, + throughput); + + return throughput < limit; +} + +/** + * batadv_v_elp_no_broadcast - checks whether a rebroadcast can be avoided + * @if_outgoing: the outgoing interface to be considered for rebroadcast + * @hardif_neigh: the hardif_neigh the packet came from + * @inverse_metric: the metric direction to use (e.g. "true" for OGMs, "false" + * for broadcast packets + * + * This function checks whether with the information available to/from ELP, a + * rebroadcast of an OGM2 or broadcast packet on an interface can be + * avoided. + * + * The inverse_metric parameter indicates whether the considered packet + * should follow the best RX (inverse_metric = "true", e.g. OGMs) or TX + * path (inverse_metric = "false", e.g. broadcast packets). + * + * Return: True, if a rebroadcast can be avoided, false otherwise. + */ +bool batadv_v_elp_no_broadcast(struct batadv_hard_iface *if_outgoing, + struct batadv_hardif_neigh_node *hardif_neigh, + bool inverse_metric) +{ + if (!if_outgoing || !hardif_neigh) + return false; + + /* ELP does not provide information across inferface domains */ + if (if_outgoing != hardif_neigh->if_incoming) + return false; + + if (!batadv_v_elp_nhh_cmp(hardif_neigh)) + return false; + + /* same neighborhood, is a better path possible? */ + if (inverse_metric) { + /* OGM2 check */ + if (batadv_v_elp_rx_ingress_bad(hardif_neigh) || + batadv_v_elp_rx_egress_bad(hardif_neigh)) + return true; + } else { + /* broadcast packet check */ + if (batadv_v_elp_tx_ingress_bad(hardif_neigh) || + batadv_v_elp_tx_egress_bad(hardif_neigh)) + return true; + } + + return false; +} + +/** + * batadv_v_elp_tvlv_handler_nhh - process incoming NHH tvlv container + * @bat_priv: the bat priv with all the soft interface information + * @tvlv_value: tvlv buffer containing the neighborhood hash data + * @tvlv_value_len: tvlv buffer length + * @ctx: handler specific context information (here: hardif_neigh) + * + * Return: NET_RX_DROP on parsing errors, NET_RX_SUCCESS otherwise. + */ +static int batadv_v_elp_tvlv_handler_nhh(struct batadv_priv *bat_priv, + void *tvlv_value, u16 tvlv_value_len, + void *ctx) +{ + struct batadv_hardif_neigh_node *hardif_neigh = ctx; + struct batadv_tvlv_nhh_data *nhh_data; + u32 min_throughput = 0; + u32 max_throughput = U32_MAX; + + if (WARN_ON(!hardif_neigh)) + return NET_RX_DROP; + + if (tvlv_value) { + if (tvlv_value_len < sizeof(*nhh_data)) + return NET_RX_DROP; + + nhh_data = (struct batadv_tvlv_nhh_data *)tvlv_value; + + memcpy(hardif_neigh->bat_v.neigh_hash, nhh_data->neigh_hash, + sizeof(hardif_neigh->bat_v.neigh_hash)); + min_throughput = ntohl(nhh_data->min_throughput); + max_throughput = ntohl(nhh_data->max_throughput); + } else { + memset(hardif_neigh->bat_v.neigh_hash, 0, + sizeof(hardif_neigh->bat_v.neigh_hash)); + } + + hardif_neigh->bat_v.min_throughput = min_throughput; + hardif_neigh->bat_v.max_throughput = max_throughput; + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Got neighbor hash on interface %s from %pM: %*phN, min_through: %u kbit/s, max_through: %u kbit/s\n", + hardif_neigh->if_incoming->net_dev->name, + hardif_neigh->addr, + (int)sizeof(hardif_neigh->bat_v.neigh_hash), + hardif_neigh->bat_v.neigh_hash, + hardif_neigh->bat_v.min_throughput * 100, + hardif_neigh->bat_v.max_throughput * 100); + + return NET_RX_SUCCESS; +} + +/** + * batadv_v_elp_mesh_init - initialize the ELP private resources for a mesh + * @bat_priv: the object representing the mesh interface to initialise + * + * Return: Always returns 0. + */ +int batadv_v_elp_mesh_init(struct batadv_priv *bat_priv) +{ + batadv_tvlv_handler_register2(bat_priv, batadv_v_elp_tvlv_handler_nhh, + BATADV_ELP, BATADV_TVLV_NHH, 1, + BATADV_TVLV_HANDLER_CIFNOTFND); + + return 0; +} + +/** + * batadv_v_elp_mesh_free - free the ELP private resources for a mesh + * @bat_priv: the object representing the mesh interface to free + */ +void batadv_v_elp_mesh_free(struct batadv_priv *bat_priv) +{ + batadv_tvlv_handler_unregister2(bat_priv, BATADV_ELP, BATADV_TVLV_NHH, + 1); +} + +/** * batadv_v_elp_init - initialize global ELP structures * * Return: A negative value on error, zero on success. diff --git a/net/batman-adv/bat_v_elp.h b/net/batman-adv/bat_v_elp.h index 2e73047..88e0507 100644 --- a/net/batman-adv/bat_v_elp.h +++ b/net/batman-adv/bat_v_elp.h @@ -20,9 +20,13 @@

#include "main.h"

+#include <linux/types.h> + struct sk_buff; struct work_struct;

+int batadv_v_elp_mesh_init(struct batadv_priv *bat_priv); +void batadv_v_elp_mesh_free(struct batadv_priv *bat_priv); int batadv_v_elp_init(void); void batadv_v_elp_free(void); int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface); @@ -32,6 +36,14 @@ void batadv_v_elp_iface_activate(struct batadv_hard_iface *primary_iface, void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *primary_iface); int batadv_v_elp_packet_recv(struct sk_buff *skb, struct batadv_hard_iface *if_incoming); +bool batadv_v_elp_nhh_cmp(struct batadv_hardif_neigh_node *hardif_neigh); +bool batadv_v_elp_rx_ingress_bad(struct batadv_hardif_neigh_node *hardif_neigh); +bool batadv_v_elp_rx_egress_bad(struct batadv_hardif_neigh_node *hardif_neigh); +bool batadv_v_elp_tx_ingress_bad(struct batadv_hardif_neigh_node *hardif_neigh); +bool batadv_v_elp_tx_egress_bad(struct batadv_hardif_neigh_node *hardif_neigh); +bool batadv_v_elp_no_broadcast(struct batadv_hard_iface *if_outgoing, + struct batadv_hardif_neigh_node *hardif_neigh, + bool inverse_metric); void batadv_v_elp_throughput_metric_update(struct work_struct *work);

#endif /* _NET_BATMAN_ADV_BAT_V_ELP_H_ */ diff --git a/net/batman-adv/bat_v_ogm.c b/net/batman-adv/bat_v_ogm.c index cfc9228..6be707d 100644 --- a/net/batman-adv/bat_v_ogm.c +++ b/net/batman-adv/bat_v_ogm.c @@ -183,7 +183,7 @@ static void batadv_v_ogm_send(struct work_struct *work) if (!kref_get_unless_zero(&hard_iface->refcount)) continue;

- ret = batadv_hardif_no_broadcast(hard_iface, NULL, NULL); + ret = batadv_hardif_no_broadcast(hard_iface, NULL, NULL, true); if (ret) { char *type;

@@ -197,6 +197,9 @@ static void batadv_v_ogm_send(struct work_struct *work) case BATADV_HARDIF_BCAST_DUPORIG: type = "single neighbor is originator"; break; + case BATADV_HARDIF_BCAST_WORSENHH: + type = "worse neighborhood metric"; + break; default: type = "unknown"; } @@ -289,10 +292,10 @@ void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *primary_iface) * * Return: the penalised throughput metric. */ -static u32 batadv_v_forward_penalty(struct batadv_priv *bat_priv, - struct batadv_hard_iface *if_incoming, - struct batadv_hard_iface *if_outgoing, - u32 throughput) +u32 batadv_v_forward_penalty(struct batadv_priv *bat_priv, + struct batadv_hard_iface *if_incoming, + struct batadv_hard_iface *if_outgoing, + u32 throughput) { int hop_penalty = atomic_read(&bat_priv->hop_penalty); int hop_penalty_max = BATADV_TQ_MAX_VALUE; @@ -752,7 +755,7 @@ static void batadv_v_ogm_process(const struct sk_buff *skb, int ogm_offset,

ret = batadv_hardif_no_broadcast(hard_iface, ogm_packet->orig, - hardif_neigh->orig); + hardif_neigh, true);

if (ret) { char *type; @@ -767,6 +770,9 @@ static void batadv_v_ogm_process(const struct sk_buff *skb, int ogm_offset, case BATADV_HARDIF_BCAST_DUPORIG: type = "single neighbor is originator"; break; + case BATADV_HARDIF_BCAST_WORSENHH: + type = "worse neighborhood metric"; + break; default: type = "unknown"; } diff --git a/net/batman-adv/bat_v_ogm.h b/net/batman-adv/bat_v_ogm.h index 2068770..f89445d 100644 --- a/net/batman-adv/bat_v_ogm.h +++ b/net/batman-adv/bat_v_ogm.h @@ -30,6 +30,10 @@ int batadv_v_ogm_iface_enable(struct batadv_hard_iface *hard_iface); struct batadv_orig_node *batadv_v_ogm_orig_get(struct batadv_priv *bat_priv, const u8 *addr); void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *primary_iface); +u32 batadv_v_forward_penalty(struct batadv_priv *bat_priv, + struct batadv_hard_iface *if_incoming, + struct batadv_hard_iface *if_outgoing, + u32 throughput); int batadv_v_ogm_packet_recv(struct sk_buff *skb, struct batadv_hard_iface *if_incoming);

diff --git a/net/batman-adv/hard-interface.c b/net/batman-adv/hard-interface.c index e348f76..c502c41 100644 --- a/net/batman-adv/hard-interface.c +++ b/net/batman-adv/hard-interface.c @@ -379,8 +379,9 @@ bool batadv_is_wifi_hardif(struct batadv_hard_iface *hard_iface) * batadv_hardif_no_broadcast - check whether (re)broadcast is necessary * @if_outgoing: the outgoing interface checked and considered for (re)broadcast * @orig_addr: the originator of this packet - * @orig_neigh: originator address of the forwarder we just got the packet from - * (NULL if we originated) + * @hardif_neigh: the neighbor we got this packet from (NULL if we originated) + * @inverse_metric: the metric direction to use (e.g. "true" for OGMs, "false" + * for broadcast packets * * Checks whether a packet needs to be (re)broadcasted on the given interface. * @@ -388,12 +389,16 @@ bool batadv_is_wifi_hardif(struct batadv_hard_iface *hard_iface) * BATADV_HARDIF_BCAST_NORECIPIENT: No neighbor on interface * BATADV_HARDIF_BCAST_DUPFWD: Just one neighbor, but it is the forwarder * BATADV_HARDIF_BCAST_DUPORIG: Just one neighbor, but it is the originator + * BATADV_HARDIF_BCAST_WORSENHH: ELP detected a worse neighborhood metric * BATADV_HARDIF_BCAST_OK: Several neighbors, must broadcast */ int batadv_hardif_no_broadcast(struct batadv_hard_iface *if_outgoing, - u8 *orig_addr, u8 *orig_neigh) + u8 *orig_addr, + struct batadv_hardif_neigh_node *hardif_neigh, + bool inverse_metric) { - struct batadv_hardif_neigh_node *hardif_neigh; + struct batadv_priv *bat_priv = netdev_priv(if_outgoing->soft_iface); + struct batadv_hardif_neigh_node *hardif_neigh_cmp; struct hlist_node *first; int ret = BATADV_HARDIF_BCAST_OK;

@@ -406,22 +411,30 @@ int batadv_hardif_no_broadcast(struct batadv_hard_iface *if_outgoing, goto out; }

- /* >1 neighbors -> (re)brodcast */ - if (rcu_dereference(hlist_next_rcu(first))) - goto out; + /* single neighbor checks */ + if (!rcu_dereference(hlist_next_rcu(first)) && hardif_neigh) { + hardif_neigh_cmp = hlist_entry(first, + struct batadv_hardif_neigh_node, + list);

- hardif_neigh = hlist_entry(first, struct batadv_hardif_neigh_node, - list); - - /* 1 neighbor, is the originator -> no rebroadcast */ - if (orig_addr && batadv_compare_eth(hardif_neigh->orig, orig_addr)) { - ret = BATADV_HARDIF_BCAST_DUPORIG; - /* 1 neighbor, is the one we received from -> no rebroadcast */ - } else if (orig_neigh && - batadv_compare_eth(hardif_neigh->orig, orig_neigh)) { - ret = BATADV_HARDIF_BCAST_DUPFWD; + /* 1 neighbor, is the originator -> no rebroadcast */ + if (batadv_compare_eth(hardif_neigh_cmp->orig, orig_addr)) { + ret = BATADV_HARDIF_BCAST_DUPORIG; + goto out; + /* 1 neighbor, is the one we received from -> no rebroadcast */ + } else if (batadv_compare_eth(hardif_neigh_cmp->orig, + hardif_neigh->orig)) { + ret = BATADV_HARDIF_BCAST_DUPFWD; + goto out; + } }

+ if (bat_priv->algo_ops->neigh.hardif_no_broadcast && + bat_priv->algo_ops->neigh.hardif_no_broadcast(if_outgoing, + hardif_neigh, + inverse_metric)) + ret = BATADV_HARDIF_BCAST_WORSENHH; + out: rcu_read_unlock(); return ret; diff --git a/net/batman-adv/hard-interface.h b/net/batman-adv/hard-interface.h index 9f9890f..931ed88 100644 --- a/net/batman-adv/hard-interface.h +++ b/net/batman-adv/hard-interface.h @@ -45,12 +45,14 @@ enum batadv_hard_if_state { * @BATADV_HARDIF_BCAST_NORECIPIENT: Broadcast not needed, there is no recipient * @BATADV_HARDIF_BCAST_DUPFWD: There is just the neighbor we got it from * @BATADV_HARDIF_BCAST_DUPORIG: There is just the originator + * @BATADV_HARDIF_BCAST_WORSENHH: ELP detected a worse neighborhood metric */ enum batadv_hard_if_bcast { BATADV_HARDIF_BCAST_OK = 0, BATADV_HARDIF_BCAST_NORECIPIENT, BATADV_HARDIF_BCAST_DUPFWD, BATADV_HARDIF_BCAST_DUPORIG, + BATADV_HARDIF_BCAST_WORSENHH, };

/** @@ -79,7 +81,9 @@ int batadv_hardif_min_mtu(struct net_device *soft_iface); void batadv_update_min_mtu(struct net_device *soft_iface); void batadv_hardif_release(struct kref *ref); int batadv_hardif_no_broadcast(struct batadv_hard_iface *if_outgoing, - u8 *orig_addr, u8 *orig_neigh); + u8 *orig_addr, + struct batadv_hardif_neigh_node *hardif_neigh, + bool inverse_metric);

/** * batadv_hardif_put - decrement the hard interface refcounter and possibly diff --git a/net/batman-adv/send.c b/net/batman-adv/send.c index 1489ec2..b60efbb 100644 --- a/net/batman-adv/send.c +++ b/net/batman-adv/send.c @@ -799,7 +799,6 @@ static void batadv_send_outstanding_bcast_packet(struct work_struct *work) unsigned long send_time = jiffies + msecs_to_jiffies(5); bool dropped = false; u8 *neigh_addr; - u8 *orig_neigh; int ret = 0;

delayed_work = to_delayed_work(work); @@ -837,10 +836,8 @@ static void batadv_send_outstanding_bcast_packet(struct work_struct *work) neigh_addr); }

- orig_neigh = neigh_node ? neigh_node->orig : NULL; - ret = batadv_hardif_no_broadcast(hard_iface, bcast_packet->orig, - orig_neigh); + neigh_node, false);

if (ret) { char *type; @@ -855,6 +852,9 @@ static void batadv_send_outstanding_bcast_packet(struct work_struct *work) case BATADV_HARDIF_BCAST_DUPORIG: type = "single neighbor is originator"; break; + case BATADV_HARDIF_BCAST_WORSENHH: + type = "worse neighborhood metric"; + break; default: type = "unknown"; } diff --git a/net/batman-adv/types.h b/net/batman-adv/types.h index 6dbdbf6..d189860 100644 --- a/net/batman-adv/types.h +++ b/net/batman-adv/types.h @@ -111,6 +111,8 @@ enum batadv_v_hard_iface_flags { * @flags: interface specific flags * @min_throughput: worst of all TX throughputs this neighbor has to others * @max_throughput: best of all TX throughputs this neighbor has to others + * @min_throughput_other: worst of all min_throughput's of other neighbors + * @max_throughput_other: worst of all max_throughput's of other neighbors * @neigh_hash: a sha512 hash of all neighbors this neighbor sees * (hash over the alphabetically ordered, concatenated, binary representation) */ @@ -123,6 +125,8 @@ struct batadv_hard_iface_bat_v { u8 flags; u32 min_throughput; u32 max_throughput; + u32 min_throughput_other; + u32 max_throughput_other; u8 neigh_hash[SHA512_DIGEST_SIZE]; };

@@ -418,6 +422,10 @@ DECLARE_EWMA(throughput, 1024, 8) * @throughput: ewma link throughput towards this neighbor * @elp_interval: time interval between two ELP transmissions * @elp_latest_seqno: latest and best known ELP sequence number + * @min_throughput: worst of all TX throughputs this neighbor has to others + * @max_throughput: best of all TX throughputs this neighbor has to others + * @neigh_hash: a sha512 hash of all neighbors this neighbor sees + * (hash over the alphabetically ordered, concatenated, binary representation) * @last_unicast_tx: when the last unicast packet has been sent to this neighbor * @metric_work: work queue callback item for metric update */ @@ -425,6 +433,9 @@ struct batadv_hardif_neigh_node_bat_v { struct ewma_throughput throughput; u32 elp_interval; u32 elp_latest_seqno; + u32 min_throughput; + u32 max_throughput; + u8 neigh_hash[SHA512_DIGEST_SIZE]; unsigned long last_unicast_tx; struct work_struct metric_work; }; @@ -1445,6 +1456,8 @@ struct batadv_algo_iface_ops { * struct batadv_algo_neigh_ops - mesh algorithm callbacks (neighbour specific) * @hardif_init: called on creation of single hop entry * (optional) + * @hardif_no_broadcast: algorithm specific check(s) regarding rebroadcasts + * (optional) * @cmp: compare the metrics of two neighbors for their respective outgoing * interfaces * @is_similar_or_better: check if neigh1 is equally similar or better than @@ -1454,6 +1467,10 @@ struct batadv_algo_iface_ops { */ struct batadv_algo_neigh_ops { void (*hardif_init)(struct batadv_hardif_neigh_node *neigh); + bool (*hardif_no_broadcast) + (struct batadv_hard_iface *if_outgoing, + struct batadv_hardif_neigh_node *hardif_neigh, + bool inverse_metric); int (*cmp)(struct batadv_neigh_node *neigh1, struct batadv_hard_iface *if_outgoing1, struct batadv_neigh_node *neigh2,