routing.c (3193e8fdfa355289892661d206d1954114a7be95) routing.c (9cfc7bd608b97463993b4f3e4775d99022253f8d)
1/*
2 * Copyright (C) 2007-2012 B.A.T.M.A.N. contributors:
1/* Copyright (C) 2007-2012 B.A.T.M.A.N. contributors:
3 *
4 * Marek Lindner, Simon Wunderlich
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of version 2 of the GNU General Public
8 * License as published by the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18 * 02110-1301, USA
2 *
3 * Marek Lindner, Simon Wunderlich
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of version 2 of the GNU General Public
7 * License as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA
19 *
20 */
21
22#include "main.h"
23#include "routing.h"
24#include "send.h"
25#include "soft-interface.h"
26#include "hard-interface.h"
27#include "icmp_socket.h"

--- 132 unchanged lines hidden (view full) ---

160 router = batadv_orig_node_get_router(orig_node);
161 if (!router)
162 goto candidate_del;
163
164 /* ... and is good enough to be considered */
165 if (neigh_node->tq_avg < router->tq_avg - BONDING_TQ_THRESHOLD)
166 goto candidate_del;
167
18 */
19
20#include "main.h"
21#include "routing.h"
22#include "send.h"
23#include "soft-interface.h"
24#include "hard-interface.h"
25#include "icmp_socket.h"

--- 132 unchanged lines hidden (view full) ---

158 router = batadv_orig_node_get_router(orig_node);
159 if (!router)
160 goto candidate_del;
161
162 /* ... and is good enough to be considered */
163 if (neigh_node->tq_avg < router->tq_avg - BONDING_TQ_THRESHOLD)
164 goto candidate_del;
165
168 /**
169 * check if we have another candidate with the same mac address or
166 /* check if we have another candidate with the same mac address or
170 * interface. If we do, we won't select this candidate because of
171 * possible interference.
172 */
173 hlist_for_each_entry_rcu(tmp_neigh_node, node,
174 &orig_node->neigh_list, list) {
175
176 if (tmp_neigh_node == neigh_node)
177 continue;
178
179 /* we only care if the other candidate is even
167 * interface. If we do, we won't select this candidate because of
168 * possible interference.
169 */
170 hlist_for_each_entry_rcu(tmp_neigh_node, node,
171 &orig_node->neigh_list, list) {
172
173 if (tmp_neigh_node == neigh_node)
174 continue;
175
176 /* we only care if the other candidate is even
180 * considered as candidate. */
177 * considered as candidate.
178 */
181 if (list_empty(&tmp_neigh_node->bonding_list))
182 continue;
183
184 if ((neigh_node->if_incoming == tmp_neigh_node->if_incoming) ||
185 (compare_eth(neigh_node->addr, tmp_neigh_node->addr))) {
186 interference_candidate = 1;
187 break;
188 }

--- 204 unchanged lines hidden (view full) ---

393 struct bat_priv *bat_priv = netdev_priv(recv_if->soft_iface);
394 struct icmp_packet_rr *icmp_packet;
395 struct ethhdr *ethhdr;
396 struct orig_node *orig_node = NULL;
397 struct neigh_node *router = NULL;
398 int hdr_size = sizeof(struct icmp_packet);
399 int ret = NET_RX_DROP;
400
179 if (list_empty(&tmp_neigh_node->bonding_list))
180 continue;
181
182 if ((neigh_node->if_incoming == tmp_neigh_node->if_incoming) ||
183 (compare_eth(neigh_node->addr, tmp_neigh_node->addr))) {
184 interference_candidate = 1;
185 break;
186 }

--- 204 unchanged lines hidden (view full) ---

391 struct bat_priv *bat_priv = netdev_priv(recv_if->soft_iface);
392 struct icmp_packet_rr *icmp_packet;
393 struct ethhdr *ethhdr;
394 struct orig_node *orig_node = NULL;
395 struct neigh_node *router = NULL;
396 int hdr_size = sizeof(struct icmp_packet);
397 int ret = NET_RX_DROP;
398
401 /**
402 * we truncate all incoming icmp packets if they don't match our size
403 */
399 /* we truncate all incoming icmp packets if they don't match our size */
404 if (skb->len >= sizeof(struct icmp_packet_rr))
405 hdr_size = sizeof(struct icmp_packet_rr);
406
407 /* drop packet if it has not necessary minimum size */
408 if (unlikely(!pskb_may_pull(skb, hdr_size)))
409 goto out;
410
411 ethhdr = (struct ethhdr *)skb_mac_header(skb);

--- 57 unchanged lines hidden (view full) ---

469 batadv_orig_node_free_ref(orig_node);
470 return ret;
471}
472
473/* In the bonding case, send the packets in a round
474 * robin fashion over the remaining interfaces.
475 *
476 * This method rotates the bonding list and increases the
400 if (skb->len >= sizeof(struct icmp_packet_rr))
401 hdr_size = sizeof(struct icmp_packet_rr);
402
403 /* drop packet if it has not necessary minimum size */
404 if (unlikely(!pskb_may_pull(skb, hdr_size)))
405 goto out;
406
407 ethhdr = (struct ethhdr *)skb_mac_header(skb);

--- 57 unchanged lines hidden (view full) ---

465 batadv_orig_node_free_ref(orig_node);
466 return ret;
467}
468
469/* In the bonding case, send the packets in a round
470 * robin fashion over the remaining interfaces.
471 *
472 * This method rotates the bonding list and increases the
477 * returned router's refcount. */
473 * returned router's refcount.
474 */
478static struct neigh_node *find_bond_router(struct orig_node *primary_orig,
479 const struct hard_iface *recv_if)
480{
481 struct neigh_node *tmp_neigh_node;
482 struct neigh_node *router = NULL, *first_candidate = NULL;
483
484 rcu_read_lock();
485 list_for_each_entry_rcu(tmp_neigh_node, &primary_orig->bond_list,

--- 16 unchanged lines hidden (view full) ---

502 if (!router && first_candidate &&
503 atomic_inc_not_zero(&first_candidate->refcount))
504 router = first_candidate;
505
506 if (!router)
507 goto out;
508
509 /* selected should point to the next element
475static struct neigh_node *find_bond_router(struct orig_node *primary_orig,
476 const struct hard_iface *recv_if)
477{
478 struct neigh_node *tmp_neigh_node;
479 struct neigh_node *router = NULL, *first_candidate = NULL;
480
481 rcu_read_lock();
482 list_for_each_entry_rcu(tmp_neigh_node, &primary_orig->bond_list,

--- 16 unchanged lines hidden (view full) ---

499 if (!router && first_candidate &&
500 atomic_inc_not_zero(&first_candidate->refcount))
501 router = first_candidate;
502
503 if (!router)
504 goto out;
505
506 /* selected should point to the next element
510 * after the current router */
507 * after the current router
508 */
511 spin_lock_bh(&primary_orig->neigh_list_lock);
512 /* this is a list_move(), which unfortunately
509 spin_lock_bh(&primary_orig->neigh_list_lock);
510 /* this is a list_move(), which unfortunately
513 * does not exist as rcu version */
511 * does not exist as rcu version
512 */
514 list_del_rcu(&primary_orig->bond_list);
515 list_add_rcu(&primary_orig->bond_list,
516 &router->bonding_list);
517 spin_unlock_bh(&primary_orig->neigh_list_lock);
518
519out:
520 rcu_read_unlock();
521 return router;
522}
523
524/* Interface Alternating: Use the best of the
525 * remaining candidates which are not using
526 * this interface.
527 *
513 list_del_rcu(&primary_orig->bond_list);
514 list_add_rcu(&primary_orig->bond_list,
515 &router->bonding_list);
516 spin_unlock_bh(&primary_orig->neigh_list_lock);
517
518out:
519 rcu_read_unlock();
520 return router;
521}
522
523/* Interface Alternating: Use the best of the
524 * remaining candidates which are not using
525 * this interface.
526 *
528 * Increases the returned router's refcount */
527 * Increases the returned router's refcount
528 */
529static struct neigh_node *find_ifalter_router(struct orig_node *primary_orig,
530 const struct hard_iface *recv_if)
531{
532 struct neigh_node *tmp_neigh_node;
533 struct neigh_node *router = NULL, *first_candidate = NULL;
534
535 rcu_read_lock();
536 list_for_each_entry_rcu(tmp_neigh_node, &primary_orig->bond_list,

--- 4 unchanged lines hidden (view full) ---

541 /* recv_if == NULL on the first node. */
542 if (tmp_neigh_node->if_incoming == recv_if)
543 continue;
544
545 if (!atomic_inc_not_zero(&tmp_neigh_node->refcount))
546 continue;
547
548 /* if we don't have a router yet
529static struct neigh_node *find_ifalter_router(struct orig_node *primary_orig,
530 const struct hard_iface *recv_if)
531{
532 struct neigh_node *tmp_neigh_node;
533 struct neigh_node *router = NULL, *first_candidate = NULL;
534
535 rcu_read_lock();
536 list_for_each_entry_rcu(tmp_neigh_node, &primary_orig->bond_list,

--- 4 unchanged lines hidden (view full) ---

541 /* recv_if == NULL on the first node. */
542 if (tmp_neigh_node->if_incoming == recv_if)
543 continue;
544
545 if (!atomic_inc_not_zero(&tmp_neigh_node->refcount))
546 continue;
547
548 /* if we don't have a router yet
549 * or this one is better, choose it. */
549 * or this one is better, choose it.
550 */
550 if ((!router) ||
551 (tmp_neigh_node->tq_avg > router->tq_avg)) {
552 /* decrement refcount of
551 if ((!router) ||
552 (tmp_neigh_node->tq_avg > router->tq_avg)) {
553 /* decrement refcount of
553 * previously selected router */
554 * previously selected router
555 */
554 if (router)
555 batadv_neigh_node_free_ref(router);
556
557 router = tmp_neigh_node;
558 atomic_inc_not_zero(&router->refcount);
559 }
560
561 batadv_neigh_node_free_ref(tmp_neigh_node);

--- 35 unchanged lines hidden (view full) ---

597
598 tt_query = (struct tt_query_packet *)skb->data;
599
600 switch (tt_query->flags & TT_QUERY_TYPE_MASK) {
601 case TT_REQUEST:
602 batadv_inc_counter(bat_priv, BAT_CNT_TT_REQUEST_RX);
603
604 /* If we cannot provide an answer the tt_request is
556 if (router)
557 batadv_neigh_node_free_ref(router);
558
559 router = tmp_neigh_node;
560 atomic_inc_not_zero(&router->refcount);
561 }
562
563 batadv_neigh_node_free_ref(tmp_neigh_node);

--- 35 unchanged lines hidden (view full) ---

599
600 tt_query = (struct tt_query_packet *)skb->data;
601
602 switch (tt_query->flags & TT_QUERY_TYPE_MASK) {
603 case TT_REQUEST:
604 batadv_inc_counter(bat_priv, BAT_CNT_TT_REQUEST_RX);
605
606 /* If we cannot provide an answer the tt_request is
605 * forwarded */
607 * forwarded
608 */
606 if (!batadv_send_tt_response(bat_priv, tt_query)) {
607 bat_dbg(DBG_TT, bat_priv,
608 "Routing TT_REQUEST to %pM [%c]\n",
609 tt_query->dst,
610 (tt_query->flags & TT_FULL_TABLE ? 'F' : '.'));
611 return route_unicast_packet(skb, recv_if);
612 }
613 break;
614 case TT_RESPONSE:
615 batadv_inc_counter(bat_priv, BAT_CNT_TT_RESPONSE_RX);
616
617 if (batadv_is_my_mac(tt_query->dst)) {
618 /* packet needs to be linearized to access the TT
609 if (!batadv_send_tt_response(bat_priv, tt_query)) {
610 bat_dbg(DBG_TT, bat_priv,
611 "Routing TT_REQUEST to %pM [%c]\n",
612 tt_query->dst,
613 (tt_query->flags & TT_FULL_TABLE ? 'F' : '.'));
614 return route_unicast_packet(skb, recv_if);
615 }
616 break;
617 case TT_RESPONSE:
618 batadv_inc_counter(bat_priv, BAT_CNT_TT_RESPONSE_RX);
619
620 if (batadv_is_my_mac(tt_query->dst)) {
621 /* packet needs to be linearized to access the TT
619 * changes */
622 * changes
623 */
620 if (skb_linearize(skb) < 0)
621 goto out;
622 /* skb_linearize() possibly changed skb->data */
623 tt_query = (struct tt_query_packet *)skb->data;
624
625 tt_size = batadv_tt_len(ntohs(tt_query->tt_data));
626
627 /* Ensure we have all the claimed data */

--- 61 unchanged lines hidden (view full) ---

689 roam_adv_packet->src, roam_adv_packet->client);
690
691 batadv_tt_global_add(bat_priv, orig_node, roam_adv_packet->client,
692 atomic_read(&orig_node->last_ttvn) + 1, true,
693 false);
694
695 /* Roaming phase starts: I have new information but the ttvn has not
696 * been incremented yet. This flag will make me check all the incoming
624 if (skb_linearize(skb) < 0)
625 goto out;
626 /* skb_linearize() possibly changed skb->data */
627 tt_query = (struct tt_query_packet *)skb->data;
628
629 tt_size = batadv_tt_len(ntohs(tt_query->tt_data));
630
631 /* Ensure we have all the claimed data */

--- 61 unchanged lines hidden (view full) ---

693 roam_adv_packet->src, roam_adv_packet->client);
694
695 batadv_tt_global_add(bat_priv, orig_node, roam_adv_packet->client,
696 atomic_read(&orig_node->last_ttvn) + 1, true,
697 false);
698
699 /* Roaming phase starts: I have new information but the ttvn has not
700 * been incremented yet. This flag will make me check all the incoming
697 * packets for the correct destination. */
701 * packets for the correct destination.
702 */
698 bat_priv->tt_poss_change = true;
699
700 batadv_orig_node_free_ref(orig_node);
701out:
702 /* returning NET_RX_DROP will make the caller function kfree the skb */
703 return NET_RX_DROP;
704}
705
706/* find a suitable router for this originator, and use
707 * bonding if possible. increases the found neighbors
703 bat_priv->tt_poss_change = true;
704
705 batadv_orig_node_free_ref(orig_node);
706out:
707 /* returning NET_RX_DROP will make the caller function kfree the skb */
708 return NET_RX_DROP;
709}
710
711/* find a suitable router for this originator, and use
712 * bonding if possible. increases the found neighbors
708 * refcount.*/
713 * refcount.
714 */
709struct neigh_node *batadv_find_router(struct bat_priv *bat_priv,
710 struct orig_node *orig_node,
711 const struct hard_iface *recv_if)
712{
713 struct orig_node *primary_orig_node;
714 struct orig_node *router_orig;
715 struct neigh_node *router;
716 static uint8_t zero_mac[ETH_ALEN] = {0, 0, 0, 0, 0, 0};
717 int bonding_enabled;
718
719 if (!orig_node)
720 return NULL;
721
722 router = batadv_orig_node_get_router(orig_node);
723 if (!router)
724 goto err;
725
726 /* without bonding, the first node should
715struct neigh_node *batadv_find_router(struct bat_priv *bat_priv,
716 struct orig_node *orig_node,
717 const struct hard_iface *recv_if)
718{
719 struct orig_node *primary_orig_node;
720 struct orig_node *router_orig;
721 struct neigh_node *router;
722 static uint8_t zero_mac[ETH_ALEN] = {0, 0, 0, 0, 0, 0};
723 int bonding_enabled;
724
725 if (!orig_node)
726 return NULL;
727
728 router = batadv_orig_node_get_router(orig_node);
729 if (!router)
730 goto err;
731
732 /* without bonding, the first node should
727 * always choose the default router. */
733 * always choose the default router.
734 */
728 bonding_enabled = atomic_read(&bat_priv->bonding);
729
730 rcu_read_lock();
731 /* select default router to output */
732 router_orig = router->orig_node;
733 if (!router_orig)
734 goto err_unlock;
735
736 if ((!recv_if) && (!bonding_enabled))
737 goto return_router;
738
739 /* if we have something in the primary_addr, we can search
735 bonding_enabled = atomic_read(&bat_priv->bonding);
736
737 rcu_read_lock();
738 /* select default router to output */
739 router_orig = router->orig_node;
740 if (!router_orig)
741 goto err_unlock;
742
743 if ((!recv_if) && (!bonding_enabled))
744 goto return_router;
745
746 /* if we have something in the primary_addr, we can search
740 * for a potential bonding candidate. */
747 * for a potential bonding candidate.
748 */
741 if (compare_eth(router_orig->primary_addr, zero_mac))
742 goto return_router;
743
744 /* find the orig_node which has the primary interface. might
749 if (compare_eth(router_orig->primary_addr, zero_mac))
750 goto return_router;
751
752 /* find the orig_node which has the primary interface. might
745 * even be the same as our router_orig in many cases */
746
753 * even be the same as our router_orig in many cases
754 */
747 if (compare_eth(router_orig->primary_addr, router_orig->orig)) {
748 primary_orig_node = router_orig;
749 } else {
750 primary_orig_node = orig_hash_find(bat_priv,
751 router_orig->primary_addr);
752 if (!primary_orig_node)
753 goto return_router;
754
755 batadv_orig_node_free_ref(primary_orig_node);
756 }
757
758 /* with less than 2 candidates, we can't do any
755 if (compare_eth(router_orig->primary_addr, router_orig->orig)) {
756 primary_orig_node = router_orig;
757 } else {
758 primary_orig_node = orig_hash_find(bat_priv,
759 router_orig->primary_addr);
760 if (!primary_orig_node)
761 goto return_router;
762
763 batadv_orig_node_free_ref(primary_orig_node);
764 }
765
766 /* with less than 2 candidates, we can't do any
759 * bonding and prefer the original router. */
767 * bonding and prefer the original router.
768 */
760 if (atomic_read(&primary_orig_node->bond_candidates) < 2)
761 goto return_router;
762
763 /* all nodes between should choose a candidate which
764 * is is not on the interface where the packet came
769 if (atomic_read(&primary_orig_node->bond_candidates) < 2)
770 goto return_router;
771
772 /* all nodes between should choose a candidate which
773 * is is not on the interface where the packet came
765 * in. */
766
774 * in.
775 */
767 batadv_neigh_node_free_ref(router);
768
769 if (bonding_enabled)
770 router = find_bond_router(primary_orig_node, recv_if);
771 else
772 router = find_ifalter_router(primary_orig_node, recv_if);
773
774return_router:

--- 309 unchanged lines hidden (view full) ---

1084 seq_diff = ntohl(bcast_packet->seqno) - orig_node->last_bcast_seqno;
1085
1086 /* check whether the packet is old and the host just restarted. */
1087 if (batadv_window_protected(bat_priv, seq_diff,
1088 &orig_node->bcast_seqno_reset))
1089 goto spin_unlock;
1090
1091 /* mark broadcast in flood history, update window position
776 batadv_neigh_node_free_ref(router);
777
778 if (bonding_enabled)
779 router = find_bond_router(primary_orig_node, recv_if);
780 else
781 router = find_ifalter_router(primary_orig_node, recv_if);
782
783return_router:

--- 309 unchanged lines hidden (view full) ---

1093 seq_diff = ntohl(bcast_packet->seqno) - orig_node->last_bcast_seqno;
1094
1095 /* check whether the packet is old and the host just restarted. */
1096 if (batadv_window_protected(bat_priv, seq_diff,
1097 &orig_node->bcast_seqno_reset))
1098 goto spin_unlock;
1099
1100 /* mark broadcast in flood history, update window position
1092 * if required. */
1101 * if required.
1102 */
1093 if (batadv_bit_get_packet(bat_priv, orig_node->bcast_bits, seq_diff, 1))
1094 orig_node->last_bcast_seqno = ntohl(bcast_packet->seqno);
1095
1096 spin_unlock_bh(&orig_node->bcast_seqno_lock);
1097
1098 /* check whether this has been sent by another originator before */
1099 if (batadv_bla_check_bcast_duplist(bat_priv, bcast_packet, hdr_size))
1100 goto out;

--- 59 unchanged lines hidden (view full) ---

1160 skb_headlen(skb));
1161 break;
1162
1163 default: /* ignore unknown packet */
1164 break;
1165 }
1166
1167 /* We take a copy of the data in the packet, so we should
1103 if (batadv_bit_get_packet(bat_priv, orig_node->bcast_bits, seq_diff, 1))
1104 orig_node->last_bcast_seqno = ntohl(bcast_packet->seqno);
1105
1106 spin_unlock_bh(&orig_node->bcast_seqno_lock);
1107
1108 /* check whether this has been sent by another originator before */
1109 if (batadv_bla_check_bcast_duplist(bat_priv, bcast_packet, hdr_size))
1110 goto out;

--- 59 unchanged lines hidden (view full) ---

1170 skb_headlen(skb));
1171 break;
1172
1173 default: /* ignore unknown packet */
1174 break;
1175 }
1176
1177 /* We take a copy of the data in the packet, so we should
1168 always free the skbuf. */
1178 * always free the skbuf.
1179 */
1169 return NET_RX_DROP;
1170}
1180 return NET_RX_DROP;
1181}