1 files changed, 371 insertions, 0 deletions

diff --git a/babeld/neighbour.c b/babeld/neighbour.c
new file mode 100644
index 0000000..d962a09
--- /dev/null
+++ b/babeld/neighbour.c
@@ -0,0 +1,371 @@
+/*
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <sys/time.h>
+#include <time.h>
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "babel_interface.h"
+#include "neighbour.h"
+#include "source.h"
+#include "route.h"
+#include "message.h"
+#include "resend.h"
+#include "babel_errors.h"
+
+struct neighbour *neighs = NULL;
+
+static struct neighbour *
+find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
+{
+    struct neighbour *neigh;
+    FOR_ALL_NEIGHBOURS(neigh) {
+        if(memcmp(address, neigh->address, 16) == 0 &&
+           neigh->ifp == ifp)
+            return neigh;
+    }
+    return NULL;
+}
+
+void
+flush_neighbour(struct neighbour *neigh)
+{
+    debugf(BABEL_DEBUG_COMMON,"Flushing neighbour %s (reach 0x%04x)",
+           format_address(neigh->address), neigh->reach);
+    flush_neighbour_routes(neigh);
+    if(unicast_neighbour == neigh)
+        flush_unicast(1);
+    flush_resends(neigh);
+
+    if(neighs == neigh) {
+        neighs = neigh->next;
+    } else {
+        struct neighbour *previous = neighs;
+        while(previous->next != neigh)
+            previous = previous->next;
+        previous->next = neigh->next;
+    }
+    free(neigh);
+}
+
+struct neighbour *
+find_neighbour(const unsigned char *address, struct interface *ifp)
+{
+    struct neighbour *neigh;
+    const struct timeval zero = {0, 0};
+
+    neigh = find_neighbour_nocreate(address, ifp);
+    if(neigh)
+        return neigh;
+
+    debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
+           format_address(address), ifp->name);
+
+    neigh = malloc(sizeof(struct neighbour));
+    if(neigh == NULL) {
+        flog_err(EC_BABEL_MEMORY, "malloc(neighbour): %s",
+		  safe_strerror(errno));
+        return NULL;
+    }
+
+    neigh->hello_seqno = -1;
+    memcpy(neigh->address, address, 16);
+    neigh->reach = 0;
+    neigh->txcost = INFINITY;
+    neigh->ihu_time = babel_now;
+    neigh->hello_time = zero;
+    neigh->hello_interval = 0;
+    neigh->ihu_interval = 0;
+    neigh->hello_send_us = 0;
+    neigh->hello_rtt_receive_time = zero;
+    neigh->rtt = 0;
+    neigh->rtt_time = zero;
+    neigh->ifp = ifp;
+    neigh->next = neighs;
+    neighs = neigh;
+    send_hello(ifp);
+    return neigh;
+}
+
+/* Recompute a neighbour's rxcost.  Return true if anything changed. */
+int
+update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
+{
+    int missed_hellos;
+    int rc = 0;
+
+    if(hello < 0) {
+        if(neigh->hello_interval == 0)
+            return rc;
+        missed_hellos =
+            ((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
+             neigh->hello_interval * 7) /
+            (neigh->hello_interval * 10);
+        if(missed_hellos <= 0)
+            return rc;
+        timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
+                          missed_hellos * neigh->hello_interval * 10);
+    } else {
+        if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
+            missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
+            if(missed_hellos < -8) {
+                /* Probably a neighbour that rebooted and lost its seqno.
+                   Reboot the universe. */
+                neigh->reach = 0;
+                missed_hellos = 0;
+                rc = 1;
+            } else if(missed_hellos < 0) {
+                if(hello_interval > neigh->hello_interval) {
+                    /* This neighbour has increased its hello interval,
+                       and we didn't notice. */
+                    neigh->reach <<= -missed_hellos;
+                    missed_hellos = 0;
+                } else {
+                    /* Late hello.  Probably due to the link layer buffering
+                       packets during a link outage.  Ignore it, but reset
+                       the expected seqno. */
+                    neigh->hello_seqno = hello;
+                    hello = -1;
+                    missed_hellos = 0;
+                }
+                rc = 1;
+            }
+        } else {
+            missed_hellos = 0;
+        }
+        neigh->hello_time = babel_now;
+        neigh->hello_interval = hello_interval;
+    }
+
+    if(missed_hellos > 0) {
+        neigh->reach >>= missed_hellos;
+        neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
+        rc = 1;
+    }
+
+    if(hello >= 0) {
+        neigh->hello_seqno = hello;
+        neigh->reach >>= 1;
+        neigh->reach |= 0x8000;
+        if((neigh->reach & 0xFC00) != 0xFC00)
+            rc = 1;
+    }
+
+    /* Make sure to give neighbours some feedback early after association */
+    if((neigh->reach & 0xBF00) == 0x8000) {
+        /* A new neighbour */
+        send_hello(neigh->ifp);
+    } else {
+        /* Don't send hellos, in order to avoid a positive feedback loop. */
+        int a = (neigh->reach & 0xC000);
+        int b = (neigh->reach & 0x3000);
+        if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
+            /* Reachability is either 1100 or 0011 */
+            send_self_update(neigh->ifp);
+        }
+    }
+
+    if((neigh->reach & 0xFC00) == 0xC000) {
+        /* This is a newish neighbour, let's request a full route dump.
+           We ought to avoid this when the network is dense */
+        send_unicast_request(neigh, NULL, 0);
+        send_ihu(neigh, NULL);
+    }
+    return rc;
+}
+
+static int
+reset_txcost(struct neighbour *neigh)
+{
+    unsigned delay;
+
+    delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
+
+    if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
+        return 0;
+
+    /* If we're losing a lot of packets, we probably lost an IHU too */
+    if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
+       (neigh->ihu_interval > 0 &&
+        delay >= neigh->ihu_interval * 10U * 10U)) {
+        neigh->txcost = INFINITY;
+        neigh->ihu_time = babel_now;
+        return 1;
+    }
+
+    return 0;
+}
+
+unsigned
+neighbour_txcost(struct neighbour *neigh)
+{
+    return neigh->txcost;
+}
+
+unsigned
+check_neighbours(void)
+{
+    struct neighbour *neigh;
+    int changed, rc;
+    unsigned msecs = 50000;
+
+    debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
+
+    neigh = neighs;
+    while(neigh) {
+        changed = update_neighbour(neigh, -1, 0);
+
+        if(neigh->reach == 0 ||
+           neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
+           timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
+            struct neighbour *old = neigh;
+            neigh = neigh->next;
+            flush_neighbour(old);
+            continue;
+        }
+
+        rc = reset_txcost(neigh);
+        changed = changed || rc;
+
+        update_neighbour_metric(neigh, changed);
+
+        if(neigh->hello_interval > 0)
+            msecs = MIN(msecs, neigh->hello_interval * 10U);
+        if(neigh->ihu_interval > 0)
+            msecs = MIN(msecs, neigh->ihu_interval * 10U);
+        neigh = neigh->next;
+    }
+
+    return msecs;
+}
+
+unsigned
+neighbour_rxcost(struct neighbour *neigh)
+{
+    unsigned delay;
+    unsigned short reach = neigh->reach;
+
+    delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
+
+    if((reach & 0xFFF0) == 0 || delay >= 180000) {
+        return INFINITY;
+    } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
+        int sreach =
+            ((reach & 0x8000) >> 2) +
+            ((reach & 0x4000) >> 1) +
+            (reach & 0x3FFF);
+        /* 0 <= sreach <= 0x7FFF */
+        int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
+        /* cost >= interface->cost */
+        if(delay >= 40000)
+            cost = (cost * (delay - 20000) + 10000) / 20000;
+        return MIN(cost, INFINITY);
+    } else {
+        /* To lose one hello is a misfortune, to lose two is carelessness. */
+        if((reach & 0xC000) == 0xC000)
+            return babel_get_if_nfo(neigh->ifp)->cost;
+        else if((reach & 0xC000) == 0)
+            return INFINITY;
+        else if((reach & 0x2000))
+            return babel_get_if_nfo(neigh->ifp)->cost;
+        else
+            return INFINITY;
+    }
+}
+
+unsigned
+neighbour_rttcost(struct neighbour *neigh)
+{
+    struct interface *ifp = neigh->ifp;
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+
+    if(!babel_ifp->max_rtt_penalty || !valid_rtt(neigh))
+        return 0;
+
+    /* Function: linear behaviour between rtt_min and rtt_max. */
+    if(neigh->rtt <= babel_ifp->rtt_min) {
+        return 0;
+    } else if(neigh->rtt <= babel_ifp->rtt_max) {
+        unsigned long long tmp =
+            (unsigned long long)babel_ifp->max_rtt_penalty *
+            (neigh->rtt - babel_ifp->rtt_min) /
+            (babel_ifp->rtt_max - babel_ifp->rtt_min);
+        assert((tmp & 0x7FFFFFFF) == tmp);
+        return tmp;
+    } else {
+        return babel_ifp->max_rtt_penalty;
+    }
+}
+
+unsigned
+neighbour_cost(struct neighbour *neigh)
+{
+    unsigned a, b, cost;
+
+    if(!if_up(neigh->ifp))
+        return INFINITY;
+
+    a = neighbour_txcost(neigh);
+
+    if(a >= INFINITY)
+        return INFINITY;
+
+    b = neighbour_rxcost(neigh);
+    if(b >= INFINITY)
+        return INFINITY;
+
+    if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
+       || (a < 256 && b < 256)) {
+        cost = a;
+    } else {
+        /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
+           probabilities of a packet getting through in the direct and reverse
+           directions. */
+        a = MAX(a, 256);
+        b = MAX(b, 256);
+        /* 1/(alpha * beta), which is just plain ETX. */
+        /* Since a and b are capped to 16 bits, overflow is impossible. */
+        cost = (a * b + 128) >> 8;
+    }
+
+    cost += neighbour_rttcost(neigh);
+
+    return MIN(cost, INFINITY);
+}
+
+int
+valid_rtt(struct neighbour *neigh)
+{
+    return (timeval_minus_msec(&babel_now, &neigh->rtt_time) < 180000) ? 1 : 0;
+}