babeld: babelz merge.

Babelz is the last version of the stand-alone babel daemon. In
particular, it use multiple channels to diminuate
interferences. Please refer to this one for more details.

1 files changed, 422 insertions, 152 deletions

diff --git a/babeld/route.c b/babeld/route.c
index aadf80f273..a9ffc5d9ab 100644
--- a/babeld/route.c
+++ b/babeld/route.c
@@ -53,36 +53,161 @@ THE SOFTWARE.
 
 static void consider_route(struct babel_route *route);
 
-struct babel_route *routes = NULL;
-int numroutes = 0, maxroutes = 0;
+struct babel_route **routes = NULL;
+static int route_slots = 0, max_route_slots = 0;
 int kernel_metric = 0;
 int allow_duplicates = -1;
+int diversity_kind = DIVERSITY_NONE;
+int diversity_factor = 256;     /* in units of 1/256 */
+int keep_unfeasible = 0;
+
+/* We maintain a list of "slots", ordered by prefix.  Every slot
+   contains a linked list of the routes to this prefix, with the
+   installed route, if any, at the head of the list. */
+
+static int
+route_compare(const unsigned char *prefix, unsigned char plen,
+               struct babel_route *route)
+{
+    int i = memcmp(prefix, route->src->prefix, 16);
+    if(i != 0)
+        return i;
+
+    if(plen < route->src->plen)
+        return -1;
+    else if(plen > route->src->plen)
+        return 1;
+    else
+        return 0;
+}
+
+/* Performs binary search, returns -1 in case of failure.  In the latter
+   case, new_return is the place where to insert the new element. */
+
+static int
+find_route_slot(const unsigned char *prefix, unsigned char plen,
+                int *new_return)
+{
+    int p, m, g, c;
+
+    if(route_slots < 1) {
+        if(new_return)
+            *new_return = 0;
+        return -1;
+    }
+
+    p = 0; g = route_slots - 1;
+
+    do {
+        m = (p + g) / 2;
+        c = route_compare(prefix, plen, routes[m]);
+        if(c == 0)
+            return m;
+        else if(c < 0)
+            g = m - 1;
+        else
+            p = m + 1;
+    } while(p <= g);
+
+    if(new_return)
+        *new_return = p;
+
+    return -1;
+}
 
 struct babel_route *
 find_route(const unsigned char *prefix, unsigned char plen,
            struct neighbour *neigh, const unsigned char *nexthop)
 {
-    int i;
-    for(i = 0; i < numroutes; i++) {
-        if(routes[i].neigh == neigh &&
-           memcmp(routes[i].nexthop, nexthop, 16) == 0 &&
-           source_match(routes[i].src, prefix, plen))
-            return &routes[i];
+    struct babel_route *route;
+    int i = find_route_slot(prefix, plen, NULL);
+
+    if(i < 0)
+        return NULL;
+
+    route = routes[i];
+
+    while(route) {
+        if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0)
+            return route;
+        route = route->next;
     }
+
     return NULL;
 }
 
 struct babel_route *
 find_installed_route(const unsigned char *prefix, unsigned char plen)
 {
-    int i;
-    for(i = 0; i < numroutes; i++) {
-        if(routes[i].installed && source_match(routes[i].src, prefix, plen))
-            return &routes[i];
-    }
+    int i = find_route_slot(prefix, plen, NULL);
+
+    if(i >= 0 && routes[i]->installed)
+        return routes[i];
+
     return NULL;
 }
 
+/* Returns an overestimate of the number of installed routes. */
+int
+installed_routes_estimate(void)
+{
+    return route_slots;
+}
+
+static int
+resize_route_table(int new_slots)
+{
+    struct babel_route **new_routes;
+    assert(new_slots >= route_slots);
+
+    if(new_slots == 0) {
+        new_routes = NULL;
+        free(routes);
+    } else {
+        new_routes = realloc(routes, new_slots * sizeof(struct babel_route*));
+        if(new_routes == NULL)
+            return -1;
+    }
+
+    max_route_slots = new_slots;
+    routes = new_routes;
+    return 1;
+}
+
+/* Insert a route into the table.  If successful, retains the route.
+   On failure, caller must free the route. */
+static struct babel_route *
+insert_route(struct babel_route *route)
+{
+    int i, n;
+
+    assert(!route->installed);
+
+    i = find_route_slot(route->src->prefix, route->src->plen, &n);
+
+    if(i < 0) {
+        if(route_slots >= max_route_slots)
+            resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
+        if(route_slots >= max_route_slots)
+            return NULL;
+        route->next = NULL;
+        if(n < route_slots)
+            memmove(routes + n + 1, routes + n,
+                    (route_slots - n) * sizeof(struct babel_route*));
+        route_slots++;
+        routes[n] = route;
+    } else {
+        struct babel_route *r;
+        r = routes[i];
+        while(r->next)
+            r = r->next;
+        r->next = route;
+        route->next = NULL;
+    }
+
+    return route;
+}
+
 void
 flush_route(struct babel_route *route)
 {
@@ -91,39 +216,67 @@ flush_route(struct babel_route *route)
     unsigned oldmetric;
     int lost = 0;
 
-    i = route - routes;
-    assert(i >= 0 && i < numroutes);
-
     oldmetric = route_metric(route);
+    src = route->src;
 
     if(route->installed) {
         uninstall_route(route);
         lost = 1;
     }
 
-    src = route->src;
+    i = find_route_slot(route->src->prefix, route->src->plen, NULL);
+    assert(i >= 0 && i < route_slots);
 
-    if(i != numroutes - 1)
-        memcpy(routes + i, routes + numroutes - 1, sizeof(struct babel_route));
-    numroutes--;
-    VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct babel_route));
+    if(route == routes[i]) {
+        routes[i] = route->next;
+        route->next = NULL;
+        free(route);
 
-    if(numroutes == 0) {
-        free(routes);
-        routes = NULL;
-        maxroutes = 0;
-    } else if(maxroutes > 8 && numroutes < maxroutes / 4) {
-        struct babel_route *new_routes;
-        int n = maxroutes / 2;
-        new_routes = realloc(routes, n * sizeof(struct babel_route));
-        if(new_routes != NULL) {
-            routes = new_routes;
-            maxroutes = n;
+        if(routes[i] == NULL) {
+            if(i < route_slots - 1)
+                memmove(routes + i, routes + i + 1,
+                        (route_slots - i - 1) * sizeof(struct babel_route*));
+            routes[route_slots - 1] = NULL;
+            route_slots--;
         }
+
+        if(route_slots == 0)
+            resize_route_table(0);
+        else if(max_route_slots > 8 && route_slots < max_route_slots / 4)
+            resize_route_table(max_route_slots / 2);
+    } else {
+        struct babel_route *r = routes[i];
+        while(r->next != route)
+            r = r->next;
+        r->next = route->next;
+        route->next = NULL;
+        free(route);
     }
 
     if(lost)
         route_lost(src, oldmetric);
+
+    release_source(src);
+}
+
+void
+flush_all_routes()
+{
+    int i;
+
+    /* Start from the end, to avoid shifting the table. */
+    i = route_slots - 1;
+    while(i >= 0) {
+        while(i < route_slots) {
+        /* Uninstall first, to avoid calling route_lost. */
+            if(routes[i]->installed)
+                uninstall_route(routes[0]);
+            flush_route(routes[i]);
+        }
+        i--;
+    }
+
+    check_sources_released();
 }
 
 void
@@ -132,12 +285,19 @@ flush_neighbour_routes(struct neighbour *neigh)
     int i;
 
     i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh == neigh) {
-            flush_route(&routes[i]);
-            continue;
+    while(i < route_slots) {
+        struct babel_route *r;
+        r = routes[i];
+        while(r) {
+            if(r->neigh == neigh) {
+                flush_route(r);
+                goto again;
+            }
+            r = r->next;
         }
         i++;
+    again:
+        ;
     }
 }
 
@@ -147,13 +307,46 @@ flush_interface_routes(struct interface *ifp, int v4only)
     int i;
 
     i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh->ifp == ifp &&
-           (!v4only || v4mapped(routes[i].nexthop))) {
-           flush_route(&routes[i]);
-           continue;
+    while(i < route_slots) {
+        struct babel_route *r;
+        r = routes[i];
+        while(r) {
+            if(r->neigh->ifp == ifp &&
+               (!v4only || v4mapped(r->nexthop))) {
+                flush_route(r);
+                goto again;
+            }
+            r = r->next;
         }
         i++;
+    again:
+        ;
+    }
+}
+
+/* Iterate a function over all routes. */
+void
+for_all_routes(void (*f)(struct babel_route*, void*), void *closure)
+{
+    int i;
+
+    for(i = 0; i < route_slots; i++) {
+        struct babel_route *r = routes[i];
+        while(r) {
+            (*f)(r, closure);
+            r = r->next;
+        }
+    }
+}
+
+void
+for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure)
+{
+    int i;
+
+    for(i = 0; i < route_slots; i++) {
+        if(routes[i]->installed)
+            (*f)(routes[i], closure);
     }
 }
 
@@ -163,10 +356,28 @@ metric_to_kernel(int metric)
     return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
 }
 
+/* This is used to maintain the invariant that the installed route is at
+   the head of the list. */
+static void
+move_installed_route(struct babel_route *route, int i)
+{
+    assert(i >= 0 && i < route_slots);
+    assert(route->installed);
+
+    if(route != routes[i]) {
+        struct babel_route *r = routes[i];
+        while(r->next != route)
+            r = r->next;
+        r->next = route->next;
+        route->next = routes[i];
+        routes[i] = route;
+    }
+}
+
 void
 install_route(struct babel_route *route)
 {
-    int rc;
+    int i, rc;
 
     if(route->installed)
         return;
@@ -175,6 +386,15 @@ install_route(struct babel_route *route)
         zlog_err("WARNING: installing unfeasible route "
                  "(this shouldn't happen).");
 
+    i = find_route_slot(route->src->prefix, route->src->plen, NULL);
+    assert(i >= 0 && i < route_slots);
+
+    if(routes[i] != route && routes[i]->installed) {
+        fprintf(stderr, "WARNING: attempting to install duplicate route "
+                "(this shouldn't happen).");
+        return;
+    }
+
     rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
                       route->nexthop,
                       route->neigh->ifp->ifindex,
@@ -186,6 +406,8 @@ install_route(struct babel_route *route)
             return;
     }
     route->installed = 1;
+    move_installed_route(route, i);
+
 }
 
 void
@@ -239,15 +461,16 @@ switch_routes(struct babel_route *old, struct babel_route *new)
 
     old->installed = 0;
     new->installed = 1;
+    move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
+                                              NULL));
 }
 
 static void
-change_route_metric(struct babel_route *route, unsigned newmetric)
+change_route_metric(struct babel_route *route,
+                    unsigned refmetric, unsigned cost, unsigned add)
 {
     int old, new;
-
-    if(route_metric(route) == newmetric)
-        return;
+    int newmetric = MIN(refmetric + cost + add, INFINITY);
 
     old = metric_to_kernel(route_metric(route));
     new = metric_to_kernel(newmetric);
@@ -265,14 +488,15 @@ change_route_metric(struct babel_route *route, unsigned newmetric)
         }
     }
 
-    route->metric = newmetric;
+    route->refmetric = refmetric;
+    route->cost = cost;
+    route->add_metric = add;
 }
 
 static void
 retract_route(struct babel_route *route)
 {
-    route->refmetric = INFINITY;
-    change_route_metric(route, INFINITY);
+    change_route_metric(route, INFINITY, INFINITY, 0);
 }
 
 int
@@ -293,6 +517,51 @@ route_expired(struct babel_route *route)
     return route->time < babel_now.tv_sec - route->hold_time;
 }
 
+static int
+channels_interfere(int ch1, int ch2)
+{
+    if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING
+       || ch2 == BABEL_IF_CHANNEL_NONINTERFERING)
+        return 0;
+    if(ch1 == BABEL_IF_CHANNEL_INTERFERING
+       || ch2 == BABEL_IF_CHANNEL_INTERFERING)
+        return 1;
+    return ch1 == ch2;
+}
+
+int
+route_interferes(struct babel_route *route, struct interface *ifp)
+{
+    struct babel_interface *babel_ifp = NULL;
+    switch(diversity_kind) {
+    case DIVERSITY_NONE:
+        return 1;
+    case DIVERSITY_INTERFACE_1:
+        return route->neigh->ifp == ifp;
+    case DIVERSITY_CHANNEL_1:
+    case DIVERSITY_CHANNEL:
+        if(route->neigh->ifp == ifp)
+            return 1;
+        babel_ifp = babel_get_if_nfo(ifp);
+        if(channels_interfere(babel_ifp->channel,
+                              babel_get_if_nfo(route->neigh->ifp)->channel))
+            return 1;
+        if(diversity_kind == DIVERSITY_CHANNEL) {
+            int i;
+            for(i = 0; i < DIVERSITY_HOPS; i++) {
+                if(route->channels[i] == 0)
+                    break;
+                if(channels_interfere(babel_ifp->channel, route->channels[i]))
+                    return 1;
+            }
+        }
+        return 0;
+    default:
+        fprintf(stderr, "Unknown kind of diversity.\n");
+        return 1;
+    }
+}
+
 int
 update_feasible(struct source *src,
                 unsigned short seqno, unsigned short refmetric)
@@ -317,21 +586,22 @@ struct babel_route *
 find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
                 struct neighbour *exclude)
 {
-    struct babel_route *route = NULL;
-    int i;
+    struct babel_route *route = NULL, *r = NULL;
+    int i = find_route_slot(prefix, plen, NULL);
+
+    if(i < 0)
+        return NULL;
+
+    route = routes[i];
 
-    for(i = 0; i < numroutes; i++) {
-        if(!source_match(routes[i].src, prefix, plen))
-            continue;
-        if(route_expired(&routes[i]))
-            continue;
-        if(feasible && !route_feasible(&routes[i]))
-            continue;
-        if(exclude && routes[i].neigh == exclude)
-            continue;
-        if(route && route_metric(route) <= route_metric(&routes[i]))
-            continue;
-        route = &routes[i];
+    r = route->next;
+    while(r) {
+        if(!route_expired(r) &&
+           (!feasible || route_feasible(r)) &&
+           (!exclude || r->neigh != exclude) &&
+           (route_metric(r) < route_metric(route)))
+            route = r;
+        r = r->next;
     }
     return route;
 }
@@ -354,31 +624,29 @@ update_route_metric(struct babel_route *route)
                                       route->src->prefix, route->src->plen,
                                       neigh->address,
                                       neigh->ifp->ifindex);
-        int newmetric = MIN(route->refmetric +
-                            add_metric +
-                            neighbour_cost(route->neigh),
-                            INFINITY);
-
-        if(newmetric != oldmetric) {
-            change_route_metric(route, newmetric);
+        change_route_metric(route, route->refmetric,
+                            neighbour_cost(route->neigh), add_metric);
+        if(route_metric(route) != oldmetric)
             route_changed(route, route->src, oldmetric);
-        }
     }
 }
 
 /* Called whenever a neighbour's cost changes, to update the metric of
- all routes through that neighbour. */
+   all routes through that neighbour.  Calls local_notify_neighbour. */
 void
 update_neighbour_metric(struct neighbour *neigh, int changed)
 {
+
     if(changed) {
         int i;
 
-        i = 0;
-        while(i < numroutes) {
-            if(routes[i].neigh == neigh)
-                update_route_metric(&routes[i]);
-            i++;
+        for(i = 0; i < route_slots; i++) {
+            struct babel_route *r = routes[i];
+            while(r) {
+                if(r->neigh == neigh)
+                    update_route_metric(r);
+                r = r->next;
+            }
         }
     }
 }
@@ -388,11 +656,13 @@ update_interface_metric(struct interface *ifp)
 {
     int i;
 
-    i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh->ifp == ifp)
-            update_route_metric(&routes[i]);
-        i++;
+    for(i = 0; i < route_slots; i++) {
+        struct babel_route *r = routes[i];
+        while(r) {
+            if(r->neigh->ifp == ifp)
+                update_route_metric(r);
+            r = r->next;
+        }
     }
 }
 
@@ -402,7 +672,8 @@ update_route(const unsigned char *router_id,
              const unsigned char *prefix, unsigned char plen,
              unsigned short seqno, unsigned short refmetric,
              unsigned short interval,
-             struct neighbour *neigh, const unsigned char *nexthop)
+             struct neighbour *neigh, const unsigned char *nexthop,
+             const unsigned char *channels, int channels_len)
 {
     struct babel_route *route;
     struct source *src;
@@ -424,12 +695,18 @@ update_route(const unsigned char *router_id,
     if(add_metric >= INFINITY)
         return NULL;
 
-    src = find_source(router_id, prefix, plen, 1, seqno);
+    route = find_route(prefix, plen, neigh, nexthop);
+
+    if(route && memcmp(route->src->id, router_id, 8) == 0)
+        /* Avoid scanning the source table. */
+        src = route->src;
+    else
+        src = find_source(router_id, prefix, plen, 1, seqno);
+
     if(src == NULL)
         return NULL;
 
     feasible = update_feasible(src, seqno, refmetric);
-    route = find_route(prefix, plen, neigh, nexthop);
     metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
 
     if(route) {
@@ -457,12 +734,12 @@ update_route(const unsigned char *router_id,
             }
         }
 
-        route->src = src;
-        if(feasible && refmetric < INFINITY)
+        route->src = retain_source(src);
+        if((feasible || keep_unfeasible) && refmetric < INFINITY)
             route->time = babel_now.tv_sec;
         route->seqno = seqno;
-        route->refmetric = refmetric;
-        change_route_metric(route, metric);
+        change_route_metric(route,
+                            refmetric, neighbour_cost(neigh), add_metric);
         route->hold_time = hold_time;
 
         route_changed(route, oldsrc, oldmetric);
@@ -472,36 +749,46 @@ update_route(const unsigned char *router_id,
         if(!feasible)
             send_unfeasible_request(neigh, route->installed && route_old(route),
                                     seqno, metric, src);
+        release_source(oldsrc);
     } else {
+        struct babel_route *new_route;
+
         if(refmetric >= INFINITY)
             /* Somebody's retracting a route we never saw. */
             return NULL;
         if(!feasible) {
             send_unfeasible_request(neigh, 0, seqno, metric, src);
-            return NULL;
-        }
-        if(numroutes >= maxroutes) {
-            struct babel_route *new_routes;
-            int n = maxroutes < 1 ? 8 : 2 * maxroutes;
-            new_routes = routes == NULL ?
-                malloc(n * sizeof(struct babel_route)) :
-                realloc(routes, n * sizeof(struct babel_route));
-            if(new_routes == NULL)
+            if(!keep_unfeasible)
                 return NULL;
-            maxroutes = n;
-            routes = new_routes;
         }
-        route = &routes[numroutes];
-        route->src = src;
+
+        route = malloc(sizeof(struct babel_route));
+        if(route == NULL) {
+            perror("malloc(route)");
+            return NULL;
+        }
+
+        route->src = retain_source(src);
         route->refmetric = refmetric;
+        route->cost = neighbour_cost(neigh);
+        route->add_metric = add_metric;
         route->seqno = seqno;
-        route->metric = metric;
         route->neigh = neigh;
         memcpy(route->nexthop, nexthop, 16);
         route->time = babel_now.tv_sec;
         route->hold_time = hold_time;
         route->installed = 0;
-        numroutes++;
+        memset(&route->channels, 0, sizeof(route->channels));
+        if(channels_len > 0)
+            memcpy(&route->channels, channels,
+                   MIN(channels_len, DIVERSITY_HOPS));
+        route->next = NULL;
+        new_route = insert_route(route);
+        if(new_route == NULL) {
+            fprintf(stderr, "Couldn't insert route.\n");
+            free(route);
+            return NULL;
+        }
         consider_route(route);
     }
     return route;
@@ -558,13 +845,6 @@ consider_route(struct babel_route *route)
     if(route_metric(installed) >= INFINITY)
         goto install;
 
-    if(route_metric(installed) >= route_metric(route) + 192)
-        goto install;
-
-    /* Avoid switching sources */
-    if(installed->src != route->src)
-        return;
-
     if(route_metric(installed) >= route_metric(route) + 64)
         goto install;
 
@@ -584,15 +864,18 @@ retract_neighbour_routes(struct neighbour *neigh)
 {
     int i;
 
-    i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh == neigh) {
-            if(routes[i].refmetric != INFINITY) {
-                unsigned short oldmetric = route_metric(&routes[i]);
-                    retract_route(&routes[i]);
+    for(i = 0; i < route_slots; i++) {
+        struct babel_route *r = routes[i];
+        while(r) {
+            if(r->neigh == neigh) {
+                if(r->refmetric != INFINITY) {
+                    unsigned short oldmetric = route_metric(r);
+                    retract_route(r);
                     if(oldmetric != INFINITY)
-                        route_changed(&routes[i], routes[i].src, oldmetric);
+                        route_changed(r, r->src, oldmetric);
+                }
             }
+            r = r->next;
         }
         i++;
     }
@@ -699,51 +982,38 @@ route_lost(struct source *src, unsigned oldmetric)
     }
 }
 
+/* This is called periodically to flush old routes.  It will also send
+   requests for routes that are about to expire. */
 void
 expire_routes(void)
 {
+    struct babel_route *r;
     int i;
 
     debugf(BABEL_DEBUG_COMMON,"Expiring old routes.");
 
     i = 0;
-    while(i < numroutes) {
-        struct babel_route *route = &routes[i];
-
-        if(route->time > babel_now.tv_sec || /* clock stepped */
-           route_old(route)) {
-            flush_route(route);
-            continue;
-        }
+    while(i < route_slots) {
+        r = routes[i];
+        while(r) {
+            /* Protect against clock being stepped. */
+            if(r->time > babel_now.tv_sec || route_old(r)) {
+                flush_route(r);
+                goto again;
+            }
 
-        update_route_metric(route);
+            update_route_metric(r);
 
-        if(route->installed && route->refmetric < INFINITY) {
-            if(route_old(route))
-                send_unicast_request(route->neigh,
-                                     route->src->prefix, route->src->plen);
+            if(r->installed && r->refmetric < INFINITY) {
+                if(route_old(r))
+                    /* Route about to expire, send a request. */
+                    send_unicast_request(r->neigh,
+                                         r->src->prefix, r->src->plen);
+            }
+            r = r->next;
         }
         i++;
+    again:
+        ;
     }
 }
-
-void
-babel_uninstall_all_routes(void)
-{
-    while(numroutes > 0) {
-        uninstall_route(&routes[0]);
-        /* We need to flush the route so network_up won't reinstall it */
-        flush_route(&routes[0]);
-    }
-}
-
-struct babel_route *
-babel_route_get_by_source(struct source *src)
-{
-    int i;
-    for(i = 0; i < numroutes; i++) {
-        if(routes[i].src == src)
-            return &routes[i];
-    }
-    return NULL;
-}