Blame view

xroute.c 11.1 KB
Juliusz Chroboczek committed
1
/*
Juliusz Chroboczek committed
2
Copyright (c) 2007, 2008 by Juliusz Chroboczek
Juliusz Chroboczek committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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.
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
Juliusz Chroboczek committed
27
#include <assert.h>
Juliusz Chroboczek committed
28
#include <sys/time.h>
Julien Cristau committed
29
#include <netinet/in.h>
Juliusz Chroboczek committed
30

Juliusz Chroboczek committed
31
#include "babeld.h"
Juliusz Chroboczek committed
32 33
#include "kernel.h"
#include "neighbour.h"
Juliusz Chroboczek committed
34
#include "message.h"
Juliusz Chroboczek committed
35 36
#include "route.h"
#include "xroute.h"
Juliusz Chroboczek committed
37
#include "util.h"
Juliusz Chroboczek committed
38
#include "configuration.h"
Juliusz Chroboczek committed
39
#include "interface.h"
Juliusz Chroboczek committed
40
#include "local.h"
Juliusz Chroboczek committed
41

Juliusz Chroboczek committed
42 43
static struct xroute *xroutes;
static int numxroutes = 0, maxxroutes = 0;
Juliusz Chroboczek committed
44 45

struct xroute *
Matthieu Boutier committed
46 47
find_xroute(const unsigned char *prefix, unsigned char plen,
            const unsigned char *src_prefix, unsigned char src_plen)
Juliusz Chroboczek committed
48 49 50
{
    int i;
    for(i = 0; i < numxroutes; i++) {
Juliusz Chroboczek committed
51
        if(xroutes[i].plen == plen &&
Matthieu Boutier committed
52 53 54
           memcmp(xroutes[i].prefix, prefix, 16) == 0 &&
           xroutes[i].src_plen == src_plen &&
           memcmp(xroutes[i].src_prefix, src_prefix, 16) == 0)
Juliusz Chroboczek committed
55
            return &xroutes[i];
Juliusz Chroboczek committed
56
    }
Juliusz Chroboczek committed
57
    return NULL;
Juliusz Chroboczek committed
58 59
}

Juliusz Chroboczek committed
60 61 62
void
flush_xroute(struct xroute *xroute)
{
Juliusz Chroboczek committed
63
    int i;
Juliusz Chroboczek committed
64

Juliusz Chroboczek committed
65 66
    i = xroute - xroutes;
    assert(i >= 0 && i < numxroutes);
Juliusz Chroboczek committed
67

Juliusz Chroboczek committed
68
    local_notify_xroute(xroute, LOCAL_FLUSH);
Juliusz Chroboczek committed
69

Juliusz Chroboczek committed
70 71
    if(i != numxroutes - 1)
        memcpy(xroutes + i, xroutes + numxroutes - 1, sizeof(struct xroute));
Juliusz Chroboczek committed
72 73
    numxroutes--;
    VALGRIND_MAKE_MEM_UNDEFINED(xroutes + numxroutes, sizeof(struct xroute));
Juliusz Chroboczek committed
74

Juliusz Chroboczek committed
75 76 77 78 79
    if(numxroutes == 0) {
        free(xroutes);
        xroutes = NULL;
        maxxroutes = 0;
    } else if(maxxroutes > 8 && numxroutes < maxxroutes / 4) {
Juliusz Chroboczek committed
80 81 82 83 84 85
        struct xroute *new_xroutes;
        int n = maxxroutes / 2;
        new_xroutes = realloc(xroutes, n * sizeof(struct xroute));
        if(new_xroutes == NULL)
            return;
        xroutes = new_xroutes;
Juliusz Chroboczek committed
86
        maxxroutes = n;
Juliusz Chroboczek committed
87
    }
Juliusz Chroboczek committed
88 89
}

Juliusz Chroboczek committed
90
int
Juliusz Chroboczek committed
91
add_xroute(unsigned char prefix[16], unsigned char plen,
Matthieu Boutier committed
92
           unsigned char src_prefix[16], unsigned char src_plen,
Juliusz Chroboczek committed
93
           unsigned short metric, unsigned int ifindex, int proto)
Juliusz Chroboczek committed
94
{
Matthieu Boutier committed
95
    struct xroute *xroute = find_xroute(prefix, plen, src_prefix, src_plen);
Juliusz Chroboczek committed
96
    if(xroute) {
Juliusz Chroboczek committed
97
        if(xroute->metric <= metric)
Juliusz Chroboczek committed
98 99
            return 0;
        xroute->metric = metric;
Juliusz Chroboczek committed
100
        local_notify_xroute(xroute, LOCAL_CHANGE);
Juliusz Chroboczek committed
101 102
        return 1;
    }
Juliusz Chroboczek committed
103

Juliusz Chroboczek committed
104 105 106
    if(numxroutes >= maxxroutes) {
        struct xroute *new_xroutes;
        int n = maxxroutes < 1 ? 8 : 2 * maxxroutes;
Juliusz Chroboczek committed
107
        new_xroutes = realloc(xroutes, n * sizeof(struct xroute));
Juliusz Chroboczek committed
108 109 110 111 112
        if(new_xroutes == NULL)
            return -1;
        maxxroutes = n;
        xroutes = new_xroutes;
    }
Juliusz Chroboczek committed
113

Juliusz Chroboczek committed
114 115
    memcpy(xroutes[numxroutes].prefix, prefix, 16);
    xroutes[numxroutes].plen = plen;
Matthieu Boutier committed
116 117
    memcpy(xroutes[numxroutes].src_prefix, src_prefix, 16);
    xroutes[numxroutes].src_plen = src_plen;
Juliusz Chroboczek committed
118 119 120 121
    xroutes[numxroutes].metric = metric;
    xroutes[numxroutes].ifindex = ifindex;
    xroutes[numxroutes].proto = proto;
    numxroutes++;
Juliusz Chroboczek committed
122
    local_notify_xroute(&xroutes[numxroutes - 1], LOCAL_ADD);
Juliusz Chroboczek committed
123 124
    return 1;
}
Juliusz Chroboczek committed
125

Juliusz Chroboczek committed
126 127 128 129 130 131 132
/* Returns an overestimate of the number of xroutes. */
int
xroutes_estimate()
{
    return numxroutes;
}

Juliusz Chroboczek committed
133 134 135 136 137 138 139
struct xroute_stream {
    int index;
};

struct
xroute_stream *
xroute_stream()
Juliusz Chroboczek committed
140
{
Juliusz Chroboczek committed
141
    struct xroute_stream *stream = calloc(1, sizeof(struct xroute_stream));
Juliusz Chroboczek committed
142
    if(stream == NULL)
Matthieu Boutier committed
143
        return NULL;
Juliusz Chroboczek committed
144 145 146 147

    return stream;
}

Juliusz Chroboczek committed
148

Juliusz Chroboczek committed
149 150 151 152 153 154 155 156 157 158 159 160 161
struct xroute *
xroute_stream_next(struct xroute_stream *stream)
{
    if(stream->index < numxroutes)
        return &xroutes[stream->index++];
    else
        return NULL;
}

void
xroute_stream_done(struct xroute_stream *stream)
{
    free(stream);
Juliusz Chroboczek committed
162 163
}

Matthieu Boutier committed
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
static int
filter_route(struct kernel_route *route, void *data) {
    void **args = (void**)data;
    int maxroutes = *(int*)args[0];
    struct kernel_route *routes = (struct kernel_route *)args[1];
    int *found = (int*)args[2];

    if(*found >= maxroutes)
        return -1;

    if(martian_prefix(route->prefix, route->plen) ||
       martian_prefix(route->src_prefix, route->src_plen))
        return 0;

    routes[*found] = *route;
    ++ *found;

    return 0;
}

static int
kernel_routes(struct kernel_route *routes, int maxroutes)
{
    int found = 0;
    void *data[3] = { &maxroutes, routes, &found };
    struct kernel_filter filter = {0};
    filter.route = filter_route;
    filter.route_closure = data;

    kernel_dump(CHANGE_ROUTE, &filter);

    return found;
}

Matthieu Boutier committed
198 199 200 201 202 203
static int
filter_address(struct kernel_addr *addr, void *data) {
    void **args = (void **)data;
    int maxroutes = *(int *)args[0];
    struct kernel_route *routes = (struct kernel_route*)args[1];
    int *found = (int *)args[2];
Matthieu Boutier committed
204
    int ifindex = *(int*)args[3];
Matthieu Boutier committed
205 206 207 208 209 210 211 212 213
    int ll = args[4] ? !!*(int*)args[4] : 0;
    struct kernel_route *route = NULL;

    if(*found >= maxroutes)
        return 0;

    if(ll == !IN6_IS_ADDR_LINKLOCAL(&addr->addr))
        return 0;

Matthieu Boutier committed
214 215
    /* ifindex may be 0 -- see kernel_addresses */
    if(ifindex && addr->ifindex != ifindex)
Matthieu Boutier committed
216 217 218 219 220 221
        return 0;

    route = &routes[*found];
    memcpy(route->prefix, addr->addr.s6_addr, 16);
    route->plen = 128;
    route->metric = 0;
Jernej Kos committed
222
    route->ifindex = addr->ifindex;
Matthieu Boutier committed
223 224 225 226 227 228 229
    route->proto = RTPROT_BABEL_LOCAL;
    memset(route->gw, 0, 16);
    ++ *found;

    return 1;
}

Matthieu Boutier committed
230 231
/* ifindex is 0 for all interfaces.  ll indicates whether we are
   interested in link-local or global addresses. */
Matthieu Boutier committed
232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
int
kernel_addresses(int ifindex, int ll, struct kernel_route *routes,
                 int maxroutes)
{
    int found = 0;
    void *data[5] = { &maxroutes, routes, &found, &ifindex, &ll };
    struct kernel_filter filter = {0};
    filter.addr = filter_address;
    filter.addr_closure = data;

    kernel_dump(CHANGE_ADDR, &filter);

    return found;
}

Juliusz Chroboczek committed
247
int
Juliusz Chroboczek committed
248
check_xroutes(int send_updates)
Juliusz Chroboczek committed
249
{
Juliusz Chroboczek committed
250
    int i, j, metric, export, change = 0, rc;
Juliusz Chroboczek committed
251
    struct kernel_route *routes;
Matthieu Boutier committed
252
    struct filter_result filter_result;
Matthieu Boutier committed
253
    int numroutes, numaddresses;
Juliusz Chroboczek committed
254
    static int maxroutes = 8;
Juliusz Chroboczek committed
255
    const int maxmaxroutes = 16 * 1024;
Juliusz Chroboczek committed
256

Juliusz Chroboczek committed
257 258
    debugf("\nChecking kernel routes.\n");

Juliusz Chroboczek committed
259
 again:
Matthieu Boutier committed
260
    routes = calloc(maxroutes, sizeof(struct kernel_route));
Juliusz Chroboczek committed
261 262 263
    if(routes == NULL)
        return -1;

Matthieu Boutier committed
264
    rc = kernel_addresses(0, 0, routes, maxroutes);
Juliusz Chroboczek committed
265
    if(rc < 0) {
Juliusz Chroboczek committed
266
        perror("kernel_addresses");
Juliusz Chroboczek committed
267
        numroutes = 0;
Juliusz Chroboczek committed
268
    } else {
Juliusz Chroboczek committed
269
        numroutes = rc;
Juliusz Chroboczek committed
270 271
    }

Juliusz Chroboczek committed
272 273 274
    if(numroutes >= maxroutes)
        goto resize;

Matthieu Boutier committed
275 276
    numaddresses = numroutes;

Juliusz Chroboczek committed
277 278 279 280 281 282 283 284
    rc = kernel_routes(routes + numroutes, maxroutes - numroutes);
    if(rc < 0)
        fprintf(stderr, "Couldn't get kernel routes.\n");
    else
        numroutes += rc;

    if(numroutes >= maxroutes)
        goto resize;
Juliusz Chroboczek committed
285

Matthieu Boutier committed
286 287 288 289 290 291 292 293 294 295 296 297 298 299
    /* Apply filter to kernel routes (e.g. change the source prefix). */

    for(i = numaddresses; i < numroutes; i++) {
        redistribute_filter(routes[i].prefix, routes[i].plen,
                            routes[i].src_prefix, routes[i].src_plen,
                            routes[i].ifindex, routes[i].proto,
                            &filter_result);
        if(filter_result.src_prefix) {
            memcpy(routes[i].src_prefix, filter_result.src_prefix, 16);
            routes[i].src_plen = filter_result.src_plen;
        }

    }

Juliusz Chroboczek committed
300
    /* Check for any routes that need to be flushed */
Juliusz Chroboczek committed
301

Juliusz Chroboczek committed
302 303
    i = 0;
    while(i < numxroutes) {
Juliusz Chroboczek committed
304
        export = 0;
Juliusz Chroboczek committed
305
        metric = redistribute_filter(xroutes[i].prefix, xroutes[i].plen,
Matthieu Boutier committed
306
                                     xroutes[i].src_prefix, xroutes[i].src_plen,
Matthieu Boutier committed
307 308
                                     xroutes[i].ifindex, xroutes[i].proto,
                                     NULL);
Juliusz Chroboczek committed
309
        if(metric < INFINITY && metric == xroutes[i].metric) {
Juliusz Chroboczek committed
310 311 312 313 314
            for(j = 0; j < numroutes; j++) {
                if(xroutes[i].plen == routes[j].plen &&
                   memcmp(xroutes[i].prefix, routes[j].prefix, 16) == 0 &&
                   xroutes[i].ifindex == routes[j].ifindex &&
                   xroutes[i].proto == routes[j].proto) {
Juliusz Chroboczek committed
315 316
                    export = 1;
                    break;
Juliusz Chroboczek committed
317
                }
Juliusz Chroboczek committed
318 319
            }
        }
Juliusz Chroboczek committed
320

Juliusz Chroboczek committed
321
        if(!export) {
Juliusz Chroboczek committed
322
            unsigned char prefix[16], plen;
Matthieu Boutier committed
323
            unsigned char src_prefix[16], src_plen;
Denis Ovsienko committed
324
            struct babel_route *route;
Juliusz Chroboczek committed
325 326
            memcpy(prefix, xroutes[i].prefix, 16);
            plen = xroutes[i].plen;
Matthieu Boutier committed
327 328
            memcpy(src_prefix, xroutes[i].src_prefix, 16);
            src_plen = xroutes[i].src_plen;
Juliusz Chroboczek committed
329
            flush_xroute(&xroutes[i]);
Matthieu Boutier committed
330
            route = find_best_route(prefix, plen, src_prefix, src_plen, 1,NULL);
Juliusz Chroboczek committed
331 332
            if(route)
                install_route(route);
Juliusz Chroboczek committed
333 334
            /* send_update_resend only records the prefix, so the update
               will only be sent after we perform all of the changes. */
Juliusz Chroboczek committed
335
            if(send_updates)
Matthieu Boutier committed
336
                send_update_resend(NULL, prefix, plen, src_prefix, src_plen);
Juliusz Chroboczek committed
337
            change = 1;
Juliusz Chroboczek committed
338 339 340 341 342
        } else {
            i++;
        }
    }

Juliusz Chroboczek committed
343 344 345
    /* Add any new routes */

    for(i = 0; i < numroutes; i++) {
Juliusz Chroboczek committed
346 347
        if(martian_prefix(routes[i].prefix, routes[i].plen))
            continue;
Juliusz Chroboczek committed
348
        metric = redistribute_filter(routes[i].prefix, routes[i].plen,
Matthieu Boutier committed
349
                                     routes[i].src_prefix, routes[i].src_plen,
Matthieu Boutier committed
350
                                     routes[i].ifindex, routes[i].proto, NULL);
Juliusz Chroboczek committed
351
        if(metric < INFINITY) {
Juliusz Chroboczek committed
352
            rc = add_xroute(routes[i].prefix, routes[i].plen,
Matthieu Boutier committed
353
                            routes[i].src_prefix, routes[i].src_plen,
Juliusz Chroboczek committed
354
                            metric, routes[i].ifindex, routes[i].proto);
Juliusz Chroboczek committed
355
            if(rc > 0) {
Denis Ovsienko committed
356
                struct babel_route *route;
Matthieu Boutier committed
357 358 359
                route = find_installed_route(routes[i].prefix, routes[i].plen,
                                             routes[i].src_prefix,
                                             routes[i].src_plen);
Juliusz Chroboczek committed
360 361 362 363 364
                if(route) {
                    if(allow_duplicates < 0 ||
                       routes[i].metric < allow_duplicates)
                        uninstall_route(route);
                }
Juliusz Chroboczek committed
365
                change = 1;
Juliusz Chroboczek committed
366
                if(send_updates)
Matthieu Boutier committed
367 368
                    send_update(NULL, 0, routes[i].prefix, routes[i].plen,
                                routes[i].src_prefix, routes[i].src_plen);
Juliusz Chroboczek committed
369
            }
Juliusz Chroboczek committed
370 371
        }
    }
Juliusz Chroboczek committed
372

Juliusz Chroboczek committed
373
    free(routes);
Juliusz Chroboczek committed
374 375
    /* Set up maxroutes for the next call. */
    maxroutes = MIN(numroutes + 8, maxmaxroutes);
Juliusz Chroboczek committed
376
    return change;
Juliusz Chroboczek committed
377 378 379 380 381 382 383

 resize:
    free(routes);
    if(maxroutes >= maxmaxroutes)
        return -1;
    maxroutes = MIN(maxmaxroutes, 2 * maxroutes);
    goto again;
Juliusz Chroboczek committed
384
}