From: Antonio Quartulli antonio@open-mesh.com
Add the support for recognising new originators in the network and rebroadcast their OGMs.
Signed-off-by: Antonio Quartulli antonio@open-mesh.com --- bat_v_elp.c | 7 +- bat_v_ogm.c | 422 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 414 insertions(+), 15 deletions(-)
diff --git a/bat_v_elp.c b/bat_v_elp.c index 1c23951..f9a6bfe 100644 --- a/bat_v_elp.c +++ b/bat_v_elp.c @@ -63,7 +63,7 @@ void batadv_elp_neigh_node_free_ref(struct batadv_elp_neigh_node *neigh) */ static struct batadv_elp_neigh_node * batadv_v_elp_neigh_new(struct batadv_hard_iface *hard_iface, - uint8_t *neigh_addr, uint8_t *orig_addr, uint32_t seqno) + uint8_t *neigh_addr, uint8_t *orig_addr) { struct batadv_elp_neigh_node *neigh;
@@ -73,7 +73,6 @@ batadv_v_elp_neigh_new(struct batadv_hard_iface *hard_iface,
memcpy(neigh->orig, orig_addr, ETH_ALEN); memcpy(neigh->addr, neigh_addr, ETH_ALEN); - neigh->last_recv_seqno = seqno - 1; neigh->last_seen = jiffies; ewma_init(&neigh->metric, 1024, 8); /* recount initialised to 2 to simplify the caller function */ @@ -326,13 +325,13 @@ static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv, neigh = batadv_v_elp_neigh_get(if_incoming, neigh_addr); if (!neigh) { neigh = batadv_v_elp_neigh_new(if_incoming, neigh_addr, - elp_packet->orig, - ntohl(elp_packet->seqno)); + elp_packet->orig); if (!neigh) goto out; }
neigh->last_seen = jiffies; + neigh->last_recv_seqno = ntohl(elp_packet->seqno);
out: if (neigh) diff --git a/bat_v_ogm.c b/bat_v_ogm.c index f66dc02..4981d7c 100644 --- a/bat_v_ogm.c +++ b/bat_v_ogm.c @@ -21,6 +21,7 @@
#include "main.h"
+#include "bat_v_elp.h" #include "bat_v_ogm.h" #include "hard-interface.h" #include "originator.h" @@ -28,6 +29,78 @@ #include "send.h" #include "translation-table.h"
+static struct batadv_orig_node * +batadv_v_ogm_orig_get(struct batadv_priv *bat_priv, const uint8_t *addr) +{ + struct batadv_orig_node *orig_node; + int hash_added; + + orig_node = batadv_orig_hash_find(bat_priv, addr); + if (orig_node) + return orig_node; + + orig_node = batadv_orig_node_new(bat_priv, addr); + + hash_added = batadv_hash_add(bat_priv->orig_hash, batadv_compare_orig, + batadv_choose_orig, orig_node, + &orig_node->hash_entry); + if (hash_added != 0) { + batadv_orig_node_free_ref(orig_node); + batadv_orig_node_free_ref(orig_node); + orig_node = NULL; + } + + return orig_node; +} + +static struct batadv_neigh_node * +batadv_v_ogm_neigh_new(struct batadv_priv *bat_priv, + struct batadv_hard_iface *hard_iface, + uint8_t *addr, + struct batadv_orig_node *orig_node, + struct batadv_orig_node *orig_neigh) +{ + struct batadv_neigh_node *neigh_node, *tmp_neigh_node; + struct batadv_elp_neigh_node *elp_neigh; + + neigh_node = batadv_neigh_node_new(hard_iface, addr, orig_neigh); + if (!neigh_node) + return NULL; + + if (!atomic_inc_not_zero(&hard_iface->refcount)) { + kfree(neigh_node); + return NULL; + } + + elp_neigh = batadv_v_elp_neigh_get(hard_iface, addr); + if (!elp_neigh) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "No ELP object for this neighbor!\n"); + return NULL; + } + + neigh_node->bat_v.elp_neigh = elp_neigh; + + spin_lock_bh(&orig_node->neigh_list_lock); + tmp_neigh_node = batadv_neigh_node_get(orig_node, hard_iface, addr); + if (!tmp_neigh_node) { + hlist_add_head_rcu(&neigh_node->list, &orig_node->neigh_list); + } else { + kfree(neigh_node); + batadv_hardif_free_ref(hard_iface); + batadv_elp_neigh_node_free_ref(elp_neigh); + neigh_node = tmp_neigh_node; + } + spin_unlock_bh(&orig_node->neigh_list_lock); + + if (!tmp_neigh_node) + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Creating new neighbor %pM for orig_node %pM on interface %s\n", + addr, orig_node->orig, hard_iface->net_dev->name); + + return neigh_node; +} + static void batadv_v_ogm_start_timer(struct batadv_priv *bat_priv) { unsigned long msecs; @@ -48,20 +121,15 @@ static void batadv_v_ogm_send_to_if(struct sk_buff *skb, struct batadv_hard_iface *hard_iface) { struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); - struct sk_buff *tmp_skb;
if (hard_iface->if_status != BATADV_IF_ACTIVE) return;
- tmp_skb = skb_clone(skb, GFP_ATOMIC); - if (!tmp_skb) - return; - batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_TX); batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES, - tmp_skb->len + ETH_HLEN); + skb->len + ETH_HLEN);
- batadv_send_skb_packet(tmp_skb, hard_iface, batadv_broadcast_addr); + batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); }
static void batadv_v_ogm_send(struct work_struct *work) @@ -70,7 +138,7 @@ static void batadv_v_ogm_send(struct work_struct *work) struct batadv_priv_bat_v *bat_v; struct batadv_priv *bat_priv; struct batadv_ogm2_packet *ogm2; - struct sk_buff *skb; + struct sk_buff *skb, *tmp_skb; unsigned char *ogm_buff, *pkt_buff; int ogm_buff_len; uint16_t tvlv_len = 0; @@ -119,7 +187,12 @@ static void batadv_v_ogm_send(struct work_struct *work) ogm2->ttl, hard_iface->net_dev->name, hard_iface->net_dev->dev_addr);
- batadv_v_ogm_send_to_if(skb, hard_iface); + /* this skb gets consumed by batadv_v_ogm_send_to_if() */ + tmp_skb = skb_clone(skb, GFP_ATOMIC); + if (!tmp_skb) + break; + + batadv_v_ogm_send_to_if(tmp_skb, hard_iface); } rcu_read_unlock();
@@ -162,11 +235,259 @@ void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *hard_iface) rcu_read_unlock(); }
+static void +batadv_v_ogm_orig_update(struct batadv_priv *bat_priv, + struct batadv_orig_node *orig_node, + struct batadv_neigh_node *neigh_node, + const struct batadv_ogm2_packet *ogm2, + struct batadv_hard_iface *if_outgoing) +{ + struct batadv_neigh_ifinfo *router_ifinfo = NULL, *neigh_ifinfo = NULL; + struct batadv_neigh_node *router = NULL; + struct batadv_orig_ifinfo *orig_ifinfo; + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "update_originator(): Searching and updating originator entry of received packet\n"); + + /* get the TVLV container and process it */ + batadv_tvlv_containers_process(bat_priv, true, orig_node, NULL, NULL, + (unsigned char *)(ogm2 + 1), + ntohs(ogm2->tvlv_len)); + + orig_node->last_seen = jiffies; + + orig_ifinfo = batadv_orig_ifinfo_new(orig_node, if_outgoing); + orig_ifinfo->last_real_seqno = ntohl(ogm2->seqno); + orig_ifinfo->last_ttl = ogm2->ttl; + batadv_orig_ifinfo_free_ref(orig_ifinfo); + + /* if this neighbor already is our next hop there is nothing + * to change + */ + router = batadv_orig_router_get(orig_node, if_outgoing); + if (router == neigh_node) + goto out; + + /* don't consider neighbours with worse metric */ + if (router) { + router_ifinfo = batadv_neigh_ifinfo_get(router, if_outgoing); + neigh_ifinfo = batadv_neigh_ifinfo_get(neigh_node, if_outgoing); + if (router_ifinfo && neigh_ifinfo && + router_ifinfo->bat_v.metric >= neigh_ifinfo->bat_v.metric) + goto out; + } + + batadv_update_route(bat_priv, orig_node, if_outgoing, neigh_node); + +out: + if (router_ifinfo) + batadv_neigh_ifinfo_free_ref(router_ifinfo); + if (neigh_ifinfo) + batadv_neigh_ifinfo_free_ref(neigh_ifinfo); + if (router) + batadv_neigh_node_free_ref(router); +} + +/** + * batadv_v_penalty - apply a penalty to the metric forwarded by the OGM + * @bat_priv: the bat priv with all the soft interface information + * @metric: the current metric value + * @link_metric: the metric of the last link traversed by the OGM + * @if_incoming: the interface where the OGM has been received + * + * Apply a penalty on the current metric value based on the characteristic of + * the interface where the OGM has been received. The return value is computed + * as follows: + * - metric * 50% if the incoming interface is wireless and the metric is not + * less than 10% of the link throughput + * - metric * (100 - hop_penalty)% otherwise + * + * Return the penalised metric value + */ +static uint32_t batadv_v_penalty(struct batadv_priv *bat_priv, + uint32_t metric, uint32_t link_metric, + struct batadv_hard_iface *if_incoming) +{ + int hop_penalty = atomic_read(&bat_priv->hop_penalty); + + /* proportion to use the same value used in batman iv (x * 128 / 256) */ + hop_penalty = hop_penalty * 100 / 255; + + if (batadv_is_wifi_netdev(if_incoming->net_dev) && + metric > link_metric / 10) + return metric / 2; + + return metric * (100 - hop_penalty) / 100; +} + +static void batadv_v_ogm_forward(struct batadv_priv *bat_priv, + const struct batadv_ogm2_packet *ogm2, + struct batadv_neigh_node *neigh_node, + struct batadv_hard_iface *if_incoming, + struct batadv_hard_iface *if_outgoing) +{ + struct batadv_ogm2_packet *ogm_new; + uint32_t link_metric, new_metric; + unsigned char *skb_buff; + struct sk_buff *skb; + uint16_t tvlv_len; + size_t packet_len; + + if (ogm2->ttl <= 1) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "ttl exceeded\n"); + return; + } + + tvlv_len = ntohs(ogm2->tvlv_len); + + packet_len = BATADV_OGM2_HLEN + tvlv_len; + skb = netdev_alloc_skb_ip_align(if_outgoing->net_dev, + ETH_HLEN + packet_len); + if (!skb) + return; + + skb_reserve(skb, ETH_HLEN); + skb_buff = skb_put(skb, packet_len); + memcpy(skb_buff, ogm2, packet_len); + + /* apply hop penalty */ + ogm_new = (struct batadv_ogm2_packet *)skb_buff; + link_metric = ewma_read(&neigh_node->bat_v.elp_neigh->metric); + new_metric = batadv_v_penalty(bat_priv, ntohl(ogm_new->metric), + link_metric, if_incoming); + ogm_new->metric = htonl(new_metric); + ogm_new->ttl--; + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Forwarding OGM2 packet on %s: metric %u, ttl %u\n", + if_outgoing->net_dev->name, new_metric, ogm_new->ttl); + + batadv_v_ogm_send_to_if(skb, if_outgoing); +} + +/** + * batadv_v_ogm_process_per_outif - process a batman iv OGM for an outgoing if + * @skb: the skb containing the OGM + * @if_incoming: the interface where this packet was received + * @if_outgoing: the interface for which the packet should be considered + */ +static void +batadv_v_ogm_process_per_outif(struct batadv_priv *bat_priv, + const struct ethhdr *ethhdr, + const struct batadv_ogm2_packet *ogm2, + struct batadv_orig_node *orig_node, + struct batadv_neigh_node *neigh_node, + struct batadv_hard_iface *if_incoming, + struct batadv_hard_iface *if_outgoing) +{ + struct batadv_neigh_ifinfo *neigh_ifinfo = NULL, *router_ifinfo = NULL; + struct batadv_neigh_node *orig_neigh_router = NULL; + struct batadv_neigh_node *router = NULL, *router_router = NULL; + struct batadv_orig_node *orig_neigh_node; + struct batadv_orig_ifinfo *orig_ifinfo = NULL; + bool is_from_best_next_hop = false; + uint32_t new_metric; + int32_t seq_diff; + + orig_ifinfo = batadv_orig_ifinfo_new(orig_node, if_outgoing); + seq_diff = ntohl(ogm2->seqno) - orig_ifinfo->last_real_seqno; + if (!hlist_empty(&orig_node->neigh_list) && + batadv_window_protected(bat_priv, seq_diff, + &orig_ifinfo->batman_seqno_reset)) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Drop packet: packet within window protection time from %pM\n", + ogm2->orig); + goto out; + } + + new_metric = ntohl(ogm2->metric); + neigh_ifinfo = batadv_neigh_ifinfo_new(neigh_node, if_outgoing); + if (seq_diff > 0 || new_metric > neigh_ifinfo->bat_v.metric) { + neigh_ifinfo->bat_v.metric = new_metric; + neigh_ifinfo->last_ttl = ogm2->ttl; + } + + router = batadv_orig_router_get(orig_node, if_outgoing); + if (router) { + router_ifinfo = batadv_neigh_ifinfo_get(router, if_outgoing); + if (router_ifinfo && (router_ifinfo->bat_v.metric != 0) && + (batadv_compare_eth(router->addr, ethhdr->h_source))) + is_from_best_next_hop = true; + } + + orig_ifinfo->last_real_seqno = ntohl(ogm2->seqno); + + /* if sender is a direct neighbor the sender mac equals + * originator mac + */ + if (router && router->orig_node == orig_node) + orig_neigh_node = orig_node; + else + orig_neigh_node = batadv_v_ogm_orig_get(bat_priv, + ethhdr->h_source); + + if (!orig_neigh_node) + goto out; + + orig_neigh_router = batadv_orig_router_get(orig_neigh_node, + if_outgoing); + + /* drop packet if sender is not a direct neighbor and if we + * don't route towards it + */ + if (router && router->orig_node != orig_node && + (!orig_neigh_router)) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Drop packet: OGM via unknown neighbor!\n"); + goto out_neigh; + } + + /* if there is a router and the sequence number is the same as the last + * received from it, but the metric is worse, then drop the packet + */ + if (router && seq_diff == 0 && new_metric < router_ifinfo->bat_v.metric) + goto out_neigh; + + batadv_v_ogm_orig_update(bat_priv, orig_node, neigh_node, ogm2, + if_outgoing); + + /* strict rule: forward packets coming from the best next hop only */ + if (router && !is_from_best_next_hop) + goto out_neigh; + + /* only forward for specific interface, not for the default one. */ + if (if_outgoing != BATADV_IF_DEFAULT) + batadv_v_ogm_forward(bat_priv, ogm2, neigh_node, if_incoming, + if_outgoing); + +out_neigh: + if (orig_neigh_node != orig_node && orig_neigh_node) + batadv_orig_node_free_ref(orig_neigh_node); +out: + if (orig_ifinfo) + batadv_orig_ifinfo_free_ref(orig_ifinfo); + if (router) + batadv_neigh_node_free_ref(router); + if (router_ifinfo) + batadv_neigh_ifinfo_free_ref(router_ifinfo); + if (router_router) + batadv_neigh_node_free_ref(router_router); + if (orig_neigh_router) + batadv_neigh_node_free_ref(orig_neigh_router); + if (neigh_ifinfo) + batadv_neigh_ifinfo_free_ref(neigh_ifinfo); +} + int batadv_v_ogm_packet_recv(struct sk_buff *skb, struct batadv_hard_iface *if_incoming) { struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); - struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb); + struct batadv_orig_node *orig_node, *orig_neigh; + uint32_t ogm_metric, link_metric, new_metric; + struct batadv_neigh_node *neigh_node = NULL; + struct ethhdr *ethhdr = eth_hdr(skb); + struct batadv_hard_iface *hard_iface; struct batadv_ogm2_packet *ogm2; + int ret = NET_RX_DROP;
/* did we receive a OGM2 packet on an interface that does not have * B.A.T.M.A.N. V enabled ? @@ -189,8 +510,87 @@ int batadv_v_ogm_packet_recv(struct sk_buff *skb, batadv_add_counter(bat_priv, BATADV_CNT_MGMT_RX_BYTES, skb->len + ETH_HLEN);
+ ogm_metric = ntohl(ogm2->metric); + + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Received OGM2 packet via NB: %pM, IF: %s [%pM] (from OG: %pM, seqno %u, metric %u, TTL %u, V %u, tvlv_len %u)\n", + ethhdr->h_source, if_incoming->net_dev->name, + if_incoming->net_dev->dev_addr, ogm2->orig, + ntohl(ogm2->seqno), ogm_metric, ogm2->ttl, + ogm2->version, ntohs(ogm2->tvlv_len)); + + /* if the metric is 0, immediately drop the packet. no need to create + * orig_node/neigh_node for a not usable route + */ + if (ogm_metric == 0) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Drop packet: originator packet with metric equal 0\n"); + return NET_RX_DROP; + } + + orig_node = batadv_v_ogm_orig_get(bat_priv, ogm2->orig); + if (!orig_node) + return NET_RX_DROP; + + orig_neigh = batadv_v_ogm_orig_get(bat_priv, ethhdr->h_source); + if (!orig_neigh) + goto out; + + neigh_node = batadv_v_ogm_neigh_new(bat_priv, if_incoming, + ethhdr->h_source, orig_node, + orig_neigh); + if (!neigh_node) { + batadv_dbg(BATADV_DBG_BATMAN, bat_priv, + "Could not create neigh node!\n"); + goto out; + } + + /* update the neigh_node information */ + neigh_node->last_seen = jiffies; + + /* update the received metric to match the node topology: if this node + * is the first hop traversed by the OGM, then the metric is substituted + * with the value of the traversed link. Otherwise the metric is + * computed as the minimum between the metric of the traversed link and + * the value contained in the OGM + */ + link_metric = ewma_read(&neigh_node->bat_v.elp_neigh->metric); + if (ogm_metric == BATADV_MAX_METRIC) + new_metric = link_metric; + else + new_metric = min_t(uint32_t, link_metric, ogm_metric); + ogm2->metric = htonl(new_metric); + + batadv_v_ogm_process_per_outif(bat_priv, ethhdr, ogm2, orig_node, + neigh_node, if_incoming, + BATADV_IF_DEFAULT); + + rcu_read_lock(); + list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { + if (hard_iface->if_status != BATADV_IF_ACTIVE) + continue; + + if (hard_iface->soft_iface != bat_priv->soft_iface) + continue; + + batadv_v_ogm_process_per_outif(bat_priv, ethhdr, ogm2, + orig_node, neigh_node, + if_incoming, hard_iface); + } + rcu_read_unlock(); + + ret = NET_RX_SUCCESS; consume_skb(skb); - return NET_RX_SUCCESS; + +out: + if (orig_node) + batadv_orig_node_free_ref(orig_node); + if (orig_neigh) + batadv_orig_node_free_ref(orig_neigh); + if (neigh_node) + batadv_neigh_node_free_ref(neigh_node); + + return ret; }
int batadv_v_ogm_init(struct batadv_priv *bat_priv)