message.c 33.4 KB
Newer Older
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1
/*
2
Copyright (c) 2007, 2008 by Juliusz Chroboczek
Juliusz Chroboczek's avatar
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 27 28 29

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 <string.h>
#include <stdio.h>
#include <assert.h>

#include <arpa/inet.h>

30
#include "babel.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
31 32
#include "util.h"
#include "net.h"
33
#include "network.h"
34
#include "source.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
35 36 37
#include "neighbour.h"
#include "route.h"
#include "xroute.h"
38
#include "resend.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
39
#include "message.h"
40
#include "filter.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
41

42
struct timeval update_flush_timeout = {0, 0};
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
43

44
const unsigned char packet_header[8] = {42, 1};
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
45 46 47 48 49

int parasitic = 0;
int silent_time = 30;
int split_horizon = 1;

50
unsigned short myseqno = 0;
51
struct timeval seqno_time = {0, 0};
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
52 53
int seqno_interval = -1;

54
struct buffered_update {
55
    unsigned char id[16];
56 57 58 59
    unsigned char prefix[16];
    unsigned char plen;
};
struct buffered_update buffered_updates[MAX_BUFFERED_UPDATES];
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
60 61 62
struct network *update_net = NULL;
int updates = 0;

63 64 65 66 67 68
#define UNICAST_BUFSIZE 1024
int unicast_buffered = 0;
unsigned char *unicast_buffer = NULL;
struct neighbour *unicast_neighbour = NULL;
struct timeval unicast_flush_timeout = {0, 0};

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
69 70 71 72 73 74 75 76 77 78
unsigned short
hash_id(const unsigned char *id)
{
    int i;
    unsigned short hash = 0;
    for(i = 0; i < 8; i++)
        hash ^= (id[2 * i] << 8) | id[2 * i + 1];
    return hash;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
79 80 81 82 83 84
void
parse_packet(const unsigned char *from, struct network *net,
             const unsigned char *packet, int len)
{
    int i, j;
    const unsigned char *message;
85 86
    unsigned char type, plen, hop_count;
    unsigned short seqno, metric;
87
    const unsigned char *address;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
88
    struct neighbour *neigh;
89 90
    int have_current_source = 0;
    unsigned char current_source[16];
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
91

92 93 94 95 96 97
    if(from[0] != 0xFE || (from[1] & 0xC0) != 0x80) {
        fprintf(stderr, "Received packet from non-local address %s.\n",
                format_address(from));
        return;
    }

98
    if(packet[0] != 42) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
99 100 101 102 103
        fprintf(stderr, "Received malformed packet on %s from %s.\n",
                net->ifname, format_address(from));
        return;
    }

104
    if(packet[1] != 1) {
105 106 107 108 109 110
        fprintf(stderr,
                "Received packet with unknown version %d on %s from %s.\n",
                packet[1], net->ifname, format_address(from));
        return;
    }

111 112 113 114 115 116
    if(len % 24 != 8) {
        fprintf(stderr, "Received malformed packet on %s from %s.\n",
                net->ifname, format_address(from));
        return;
    }

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
117
    j = 0;
118 119 120 121
    for(i = 0; i < (len - 8) / 24; i++) {
        message = packet + 8 + 24 * i;
        type = message[0];
        plen = message[1];
122
        hop_count = message[3];
123 124 125 126 127 128
        seqno = ntohs(*(uint16_t*)(message + 4));
        metric = ntohs(*(uint16_t*)(message + 6));
        address = message + 8;
        if(type == 0) {
            int changed;
            if(memcmp(address, myid, 16) == 0)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
129
                continue;
130 131
            debugf("Received hello (%d) on %s from %s (%s).\n",
                   metric, net->ifname,
132
                   format_address(address),
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
133
                   format_address(from));
134
            net->activity_time = now.tv_sec;
135
            update_hello_interval(net);
136
            neigh = add_neighbour(address, from, net);
137 138
            if(neigh == NULL)
                continue;
139 140 141
            changed = update_neighbour(neigh, seqno, metric);
            if(changed)
                update_neighbour_metric(neigh);
142 143
            if(metric > 0)
                schedule_neighbours_check(metric * 10, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
144 145
        } else {
            neigh = find_neighbour(from, net);
146 147 148
            if(neigh == NULL) {
                debugf("Received message from unknown neighbour %s.\n",
                       format_address(from));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
149
                continue;
150
            }
151
            net->activity_time = now.tv_sec;
152
            if(type == 1) {
153
                debugf("Received ihu %d for %s from %s (%s) %d.\n",
154
                       metric,
155 156
                       format_address(address),
                       format_address(neigh->id),
157
                       format_address(from), seqno);
158
                if(memcmp(myid, address, 16) == 0) {
159
                    neigh->txcost = metric;
160
                    neigh->ihu_time = now;
161
                    neigh->ihu_interval = seqno;
162
                    update_neighbour_metric(neigh);
163 164
                    if(seqno > 0)
                        schedule_neighbours_check(seqno * 10 * 3, 0);
165 166
                }
            } else if(type == 2) {
167
                debugf("Received request on %s from %s (%s) for %s "
168
                       "(%d hops).\n",
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
169 170 171
                       net->ifname,
                       format_address(neigh->id),
                       format_address(from),
172 173 174
                       plen == 0xFF ?
                       "any" :
                       format_prefix(address, plen),
175
                       hop_count);
176
                if(plen == 0xFF) {
177
                    /* If a neighbour is requesting a full route dump from us,
178
                       we might as well send it an IHU. */
179
                    send_ihu(neigh, NULL);
180
                    send_update(neigh->network, 0, NULL, 0);
181
                } else {
182 183
                    handle_request(neigh, address, plen,
                                   hop_count, seqno, metric);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
184
                }
185 186 187
            } else if(type == 3) {
                if(plen == 0xFF)
                    debugf("Received update for %s/none on %s from %s (%s).\n",
188
                           format_address(address),
189 190 191 192 193
                           net->ifname,
                           format_address(neigh->id),
                           format_address(from));
                else
                    debugf("Received update for %s on %s from %s (%s).\n",
194
                           format_prefix(address, plen),
195 196 197 198 199 200 201
                           net->ifname,
                           format_address(neigh->id),
                           format_address(from));
                memcpy(current_source, address, 16);
                have_current_source = 1;
                if(memcmp(address, myid, 16) == 0)
                    continue;
202 203 204
                if(plen <= 128) {
                    unsigned char prefix[16];
                    mask_prefix(prefix, address, plen);
205 206
                    update_route(address, prefix, plen, seqno, metric, neigh,
                                 neigh->address);
207
                }
208
            } else if(type == 4) {
209
                unsigned char prefix[16];
210 211
                debugf("Received prefix %s on %s from %s (%s).\n",
                       format_prefix(address, plen),
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
212 213 214
                       net->ifname,
                       format_address(neigh->id),
                       format_address(from));
215 216 217 218 219 220
                if(!have_current_source) {
                    fprintf(stderr, "Received prefix with no source "
                            "on %s from %s (%s).\n",
                            net->ifname,
                            format_address(neigh->id),
                            format_address(from));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
221 222
                    continue;
                }
223 224
                if(memcmp(current_source, myid, 16) == 0)
                    continue;
225
                mask_prefix(prefix, address, plen);
226 227
                update_route(current_source, prefix, plen, seqno, metric,
                             neigh, neigh->address);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
228 229
            } else if(type == 5) {
                unsigned char p4[16], prefix[16], nh[16];
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
230
                if(!net->ipv4)
231
                    continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
232 233
                v4tov6(p4, message + 20);
                v4tov6(nh, message + 16);
234
                debugf("Received update for %s nh %s on %s from %s (%s).\n",
235
                       format_prefix(p4, plen + 96),
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
236 237 238 239 240 241
                       format_address(nh),
                       net->ifname,
                       format_address(neigh->id),
                       format_address(from));
                if(plen > 32)
                    continue;
242 243 244 245 246 247
                if(!have_current_source) {
                    fprintf(stderr, "Received IPv4 prefix with no source "
                            "on %s from %s (%s).\n",
                            net->ifname,
                            format_address(neigh->id),
                            format_address(from));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
248
                    continue;
249
                }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
250 251 252 253 254
                if(memcmp(current_source, myid, 16) == 0)
                    continue;
                mask_prefix(prefix, p4, plen + 96);
                update_route(current_source, prefix, plen + 96, seqno, metric,
                             neigh, nh);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
255
            } else {
256 257
                debugf("Received unknown packet type %d from %s (%s).\n",
                       type, format_address(neigh->id), format_address(from));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
258 259 260 261 262 263
            }
        }
    }
    return;
}

264
void
265 266 267 268
handle_request(struct neighbour *neigh, const unsigned char *prefix,
               unsigned char plen, unsigned char hop_count,
               unsigned short seqno, unsigned short router_hash)
{
269
    struct xroute *xroute;
270
    struct route *route;
271
    struct neighbour *successor = NULL;
272

273
    xroute = find_xroute(prefix, plen);
274
    if(xroute) {
275
        if(hop_count > 0 && router_hash == hash_id(myid)) {
276 277 278 279 280
            if(seqno_compare(seqno, myseqno) > 0) {
                if(seqno_minus(seqno, myseqno) > 100) {
                    /* Hopelessly out-of-date request */
                    return;
                }
281
                update_myseqno(1);
282
            }
283
        }
284 285 286 287 288
        send_update(neigh->network, 1, prefix, plen);
        return;
    }

    route = find_installed_route(prefix, plen);
289 290 291
    if(route &&
       (hop_count == 0 ||
        (route->metric < INFINITY &&
292
         (router_hash != hash_id(route->src->id) ||
293 294 295 296 297 298 299
          seqno_compare(seqno, route->seqno) <= 0)))) {
        /* We can satisfy this request straight away.  Note that in the
           hop_count=0 case, we do send a recent retraction, in order to
           reply to nodes whose routes are about to expire. */
        send_update(neigh->network, 1, prefix, plen);
        return;
    }
300

301 302
    if(hop_count <= 1)
        return;
303

304
    if(route && router_hash == hash_id(route->src->id) &&
305 306 307 308 309
       seqno_minus(seqno, route->seqno) > 100) {
        /* Hopelessly out-of-date */
        return;
    }

310 311 312
    if(request_redundant(neigh->network, prefix, plen, seqno, router_hash))
        return;

313
    /* Let's try to forward this request. */
314 315
    if(route && route->metric < INFINITY)
        successor = route->neigh;
316

317
    if(!successor || successor == neigh) {
318
        /* We were about to forward a request to its requestor.  Try to
319
           find a different neighbour to forward the request to. */
320
        struct route *other_route;
321

322 323 324 325
        other_route = find_best_route(prefix, plen, 0, neigh);
        if(other_route && other_route->metric < INFINITY)
            successor = other_route->neigh;
    }
326

327 328
    if(!successor || successor == neigh)
        /* Give up */
329 330
        return;

331 332
    send_unicast_request(successor, prefix, plen, hop_count - 1,
                         seqno, router_hash);
333 334
    record_resend(RESEND_REQUEST, prefix, plen, seqno, router_hash,
                  neigh->network, 0);
335 336 337
}


338 339
/* Under normal circumstances, there are enough moderation mechanisms
   elsewhere in the protocol to make sure that this last-ditch check
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
340
   should never trigger.  But I'm supersticious. */
341 342 343 344

static int
check_bucket(struct network *net)
{
345 346 347 348 349 350 351 352
    if(net->bucket <= 0) {
        int seconds = now.tv_sec - net->bucket_time;
        if(seconds > 0) {
            net->bucket = MIN(BUCKET_TOKENS_MAX,
                              seconds * BUCKET_TOKENS_PER_SEC);
        }
        /* Reset bucket time unconditionally, in case clock is stepped. */
        net->bucket_time = now.tv_sec;
353 354
    }

355 356
    if(net->bucket > 0) {
        net->bucket--;
357 358 359 360 361 362
        return 1;
    } else {
        return 0;
    }
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
363 364 365 366 367 368
void
flushbuf(struct network *net)
{
    int rc;
    struct sockaddr_in6 sin6;

369 370 371
    assert(net->buffered <= net->bufsize);

    if(update_net == net)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
372 373 374 375 376
        flushupdates();

    if(net->buffered > 0) {
        debugf("  (flushing %d buffered bytes on %s)\n",
               net->buffered, net->ifname);
377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
        if(check_bucket(net)) {
            memset(&sin6, 0, sizeof(sin6));
            sin6.sin6_family = AF_INET6;
            memcpy(&sin6.sin6_addr, protocol_group, 16);
            sin6.sin6_port = htons(protocol_port);
            sin6.sin6_scope_id = net->ifindex;
            rc = babel_send(protocol_socket,
                            packet_header, sizeof(packet_header),
                            net->sendbuf, net->buffered,
                            (struct sockaddr*)&sin6, sizeof(sin6));
            if(rc < 0)
                perror("send");
        } else {
            fprintf(stderr, "Warning: bucket full, dropping packet to %s.\n",
                    net->ifname);
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
393 394 395
    }
    VALGRIND_MAKE_MEM_UNDEFINED(net->sendbuf, net->bufsize);
    net->buffered = 0;
396 397
    net->flush_timeout.tv_sec = 0;
    net->flush_timeout.tv_usec = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
398 399 400 401 402
}

static void
schedule_flush(struct network *net)
{
403
    int msecs = jitter(net, 0);
404 405
    if(net->flush_timeout.tv_sec != 0 &&
       timeval_minus_msec(&net->flush_timeout, &now) < msecs)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
406
        return;
407
    net->flush_timeout.tv_usec = (now.tv_usec + msecs * 1000) % 1000000;
408 409
    net->flush_timeout.tv_sec =
        now.tv_sec + (now.tv_usec / 1000 + msecs) / 1000;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
410 411
}

412 413 414
void
schedule_flush_now(struct network *net)
{
415
    /* Almost now */
416
    int msecs = roughly(10);
417 418
    if(net->flush_timeout.tv_sec != 0 &&
       timeval_minus_msec(&net->flush_timeout, &now) < msecs)
419
        return;
420 421 422
    net->flush_timeout.tv_usec = (now.tv_usec + msecs * 1000) % 1000000;
    net->flush_timeout.tv_sec =
        now.tv_sec + (now.tv_usec / 1000 + msecs) / 1000;
423 424
}

425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440
static void
schedule_unicast_flush(void)
{
    int msecs;

    if(!unicast_neighbour)
        return;
    msecs = jitter(unicast_neighbour->network, 1);
    if(unicast_flush_timeout.tv_sec != 0 &&
       timeval_minus_msec(&unicast_flush_timeout, &now) < msecs)
        return;
    unicast_flush_timeout.tv_usec = (now.tv_usec + msecs * 1000) % 1000000;
    unicast_flush_timeout.tv_sec =
        now.tv_sec + (now.tv_usec / 1000 + msecs) / 1000;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
441 442 443
static void
start_message(struct network *net, int bytes)
{
444
    assert(net->buffered % 24 == 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
445 446 447 448
    if(net->bufsize - net->buffered < bytes)
        flushbuf(net);
}

449 450
static void
send_message(struct network *net,
451
             unsigned char type,  unsigned char plen, unsigned char hop_count,
452 453 454
             unsigned short seqno, unsigned short metric,
             const unsigned char *address)
{
455 456 457
    unsigned char *buf;
    int n;

458
    if(!net->up)
459 460
        return;

461
    start_message(net, 24);
462 463 464 465 466 467 468 469 470 471 472 473 474 475 476
    buf = net->sendbuf;
    n = net->buffered;

    buf[n++] = type;
    buf[n++] = plen;
    buf[n++] = 0;
    buf[n++] = hop_count;
    buf[n++] = (seqno >> 8) & 0xFF;
    buf[n++] = seqno & 0xFF;
    buf[n++] = (metric >> 8) & 0xFF;
    buf[n++] = metric & 0xFF;
    memcpy(buf + n, address, 16);
    n += 16;
    net->buffered = n;

477 478 479
    schedule_flush(net);
}

480 481 482 483 484 485 486 487
/* Flush buffers if they contain any hellos.  This avoids sending multiple
   hellos in a single packet, which breaks link quality estimation. */
int
flush_hellos(struct network *net)
{
    int i;
    assert(net->buffered % 24 == 0);

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
488
    for(i = 0; i < net->buffered / 24; i++) {
489 490 491 492 493 494 495 496 497 498
        const unsigned char *message;
        message = (const unsigned char*)(net->sendbuf + i * 24);
        if(message[0] == 0) {
            flushbuf(net);
            return 1;
        }
    }
    return 0;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
499
void
500
send_hello_noupdate(struct network *net, unsigned interval)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
501
{
502
    debugf("Sending hello (%d) to %s.\n", interval, net->ifname);
503
    net->hello_seqno = seqno_plus(net->hello_seqno, 1);
504
    flush_hellos(net);
505
    delay_jitter(&net->hello_time, &net->hello_timeout,
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
506
                 net->hello_interval);
507
    send_message(net, 0, 0, 0, net->hello_seqno,
508
                 interval > 0xFFFF ? 0 : interval,
509
                 myid);
510 511 512 513 514 515 516
}

void
send_hello(struct network *net)
{
    int changed;
    changed = update_hello_interval(net);
517
    send_hello_noupdate(net, (net->hello_interval + 9) / 10);
518 519
    /* Send full IHU every 3 hellos, and marginal IHU each time */
    if(changed || net->hello_seqno % 3 == 0)
520
        send_ihu(NULL, net);
521 522
    else
        send_marginal_ihu(net);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
523 524 525
}

void
526
send_request(struct network *net,
527 528 529
             const unsigned char *prefix, unsigned char plen,
             unsigned char hop_count, unsigned short seqno,
             unsigned short router_hash)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
530 531
{
    if(net == NULL) {
532 533 534
        struct network *n;
        FOR_ALL_NETS(n) {
            if(n->up)
535
                continue;
536
            send_request(n, prefix, plen, hop_count, seqno, router_hash);
537
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
538 539 540
        return;
    }

541 542 543 544
    /* Make sure any buffered updates go out before this request. */
    if(!net || update_net == net)
        flushupdates();

545 546 547
    debugf("Sending request to %s for %s (%d hops).\n",
           net->ifname, prefix ? format_prefix(prefix, plen) : "any",
           hop_count);
548
    if(prefix)
549
        send_message(net, 2, plen, hop_count, seqno, router_hash, prefix);
550
    else
551
        send_message(net, 2, 0xFF, 0, 0, 0, ones);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
552 553
}

554
void
555 556
send_request_resend(struct neighbour *neigh,
                    const unsigned char *prefix, unsigned char plen,
557 558
                    unsigned short seqno, unsigned short router_hash)
{
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
559
    int delay;
560

561 562 563 564 565
    if(neigh)
        send_unicast_request(neigh, prefix, plen, 127, seqno, router_hash);
    else
        send_request(NULL, prefix, plen, 127, seqno, router_hash);

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
566 567 568 569
    delay = 2000;
    delay = MIN(delay, wireless_hello_interval / 2);
    delay = MIN(delay, wired_hello_interval / 2);
    delay = MAX(delay, 10);
570
    record_resend(RESEND_REQUEST, prefix, plen, seqno, router_hash,
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
571
                   neigh ? neigh->network : NULL, delay);
572

573 574
}

575 576
void
flush_unicast(int dofree)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
577 578 579 580
{
    struct sockaddr_in6 sin6;
    int rc;

581 582 583 584 585
    if(unicast_buffered == 0)
        goto done;

    if(!unicast_neighbour->network->up)
        goto done;
586

587 588 589 590
    /* Preserve ordering of messages */
    flushbuf(unicast_neighbour->network);

    if(check_bucket(unicast_neighbour->network)) {
591 592
        memset(&sin6, 0, sizeof(sin6));
        sin6.sin6_family = AF_INET6;
593
        memcpy(&sin6.sin6_addr, unicast_neighbour->address, 16);
594
        sin6.sin6_port = htons(protocol_port);
595
        sin6.sin6_scope_id = unicast_neighbour->network->ifindex;
596 597
        rc = babel_send(protocol_socket,
                        packet_header, sizeof(packet_header),
598
                        unicast_buffer, unicast_buffered,
599 600 601 602
                        (struct sockaddr*)&sin6, sizeof(sin6));
        if(rc < 0)
            perror("send(unicast)");
    } else {
603 604 605 606 607 608
        fprintf(stderr,
                "Warning: bucket full, dropping unicast packet"
                "to %s (%s) if %s.\n",
                format_address(unicast_neighbour->id),
                format_address(unicast_neighbour->address),
                unicast_neighbour->network->ifname);
609
    }
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643

 done:
    VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE);
    unicast_buffered = 0;
    if(dofree && unicast_buffer) {
        free(unicast_buffer);
        unicast_buffer = NULL;
    }
    unicast_neighbour = NULL;
    unicast_flush_timeout.tv_sec = 0;
    unicast_flush_timeout.tv_usec = 0;
}

static void
send_unicast_message(struct neighbour *neigh,
                     unsigned char type,
                     unsigned char plen, unsigned char hop_count,
                     unsigned short seqno, unsigned short metric,
                     const unsigned char *address)
{
    if(unicast_neighbour) {
        if(neigh != unicast_neighbour ||
           unicast_buffered + 24 >=
           MIN(UNICAST_BUFSIZE, neigh->network->bufsize))
        flush_unicast(0);
    }

    if(!unicast_buffer)
        unicast_buffer = malloc(UNICAST_BUFSIZE);
    if(!unicast_buffer) {
        perror("malloc(unicast_buffer)");
        return;
    }

644 645
    unicast_neighbour = neigh;

646
    assert(unicast_buffered % 24 == 0);
647

648 649 650 651 652 653 654 655 656 657 658 659
    unicast_buffer[unicast_buffered++] = type;
    unicast_buffer[unicast_buffered++] = plen;
    unicast_buffer[unicast_buffered++] = 0;
    unicast_buffer[unicast_buffered++] = hop_count;
    unicast_buffer[unicast_buffered++] = (seqno >> 8) & 0xFF;
    unicast_buffer[unicast_buffered++] = seqno & 0xFF;
    unicast_buffer[unicast_buffered++] = (metric >> 8) & 0xFF;
    unicast_buffer[unicast_buffered++] = metric & 0xFF;
    memcpy(unicast_buffer + unicast_buffered, address, 16);
    unicast_buffered += 16;

    schedule_unicast_flush();
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
660 661 662
}

void
663
send_unicast_request(struct neighbour *neigh,
664 665 666
                     const unsigned char *prefix, unsigned char plen,
                     unsigned char hop_count, unsigned short seqno,
                     unsigned short router_hash)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
667
{
668 669 670 671
    /* Make sure any buffered updates go out before this request. */
    if(update_net == neigh->network)
        flushupdates();

672
    debugf("Sending unicast request to %s (%s) for %s (%d hops).\n",
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
673 674
           format_address(neigh->id),
           format_address(neigh->address),
675 676
           prefix ? format_prefix(prefix, plen) : "any",
           hop_count);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
677

678 679 680 681 682
    if(prefix)
        send_unicast_message(neigh,
                             2, plen, hop_count, seqno, router_hash, prefix);
    else
        send_unicast_message(neigh, 2, 0xFF, 0, 0, 0, ones);
683
}
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
684

685 686 687 688 689 690 691 692 693 694 695 696 697
/* Return the source-id of the last buffered update message. */
static const unsigned char *
message_source_id(struct network *net)
{
    int i;
    assert(net->buffered % 24 == 0);

    i = net->buffered / 24 - 1;
    while(i >= 0) {
        const unsigned char *message;
        message = (const unsigned char*)(net->sendbuf + i * 24);
        if(message[0] == 3)
            return message + 8;
698
        else if(message[0] == 4 || message[0] == 5)
699 700 701 702 703 704 705 706
            i--;
        else
            break;
    }

    return NULL;
}

707 708
static void
really_send_update(struct network *net,
709
                   const unsigned char *id,
710
                   const unsigned char *prefix, unsigned char plen,
711
                   unsigned short seqno, unsigned short metric)
712
{
713 714
    int add_metric;

715 716 717
    if(!net->up)
        return;

718
    add_metric = output_filter(id, prefix, plen, net->ifindex);
719 720

    if(add_metric < INFINITY) {
721
        metric = MIN(metric + add_metric, INFINITY);
722
        if(plen >= 96 && v4mapped(prefix)) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
723 724
            const unsigned char *sid;
            unsigned char v4route[16];
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
725
            if(!net->ipv4)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
726 727
                return;
            memset(v4route, 0, 8);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
728
            memcpy(v4route + 8, net->ipv4, 4);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
729 730 731
            memcpy(v4route + 12, prefix + 12, 4);
            start_message(net, 48);
            sid = message_source_id(net);
732 733
            if(sid == NULL || memcmp(id, sid, 16) != 0)
                send_message(net, 3, 0xFF, 0, 0, 0xFFFF, id);
734
            send_message(net, 5, plen - 96, 0, seqno, metric, v4route);
735
        } else {
736 737
            if(in_prefix(id, prefix, plen)) {
                send_message(net, 3, plen, 0, seqno, metric, id);
738
            } else {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
739
                const unsigned char *sid;
740 741
                start_message(net, 48);
                sid = message_source_id(net);
742 743
                if(sid == NULL || memcmp(id, sid, 16) != 0)
                    send_message(net, 3, 0xFF, 0, 0, 0xFFFF, id);
744
                send_message(net, 4, plen, 0, seqno, metric, prefix);
745
            }
746
        }
747
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
748 749
}

750 751 752 753
static int
compare_buffered_updates(const void *av, const void *bv)
{
    const struct buffered_update *a = av, *b = bv;
754
    int rc, v4a, v4b, ipa, ipb;
755 756 757 758 759 760 761 762 763 764

    rc = memcmp(a->id, b->id, 16);
    if(rc != 0)
        return rc;

    v4a = (a->plen >= 96 && v4mapped(a->prefix));
    v4b = (b->plen >= 96 && v4mapped(b->prefix));

    if(v4a > v4b)
        return 1;
765
    else if(v4a < v4b)
766 767
        return -1;

768 769 770 771 772 773 774 775
    ipa = in_prefix(a->id, a->prefix, a->plen);
    ipb = in_prefix(b->id, b->prefix, b->plen);

    if(ipa > ipb)
        return -1;
    else if(ipa < ipb)
        return 1;

776 777 778 779 780 781
    if(a->plen < b->plen)
        return -1;
    else if(a->plen > b->plen)
        return 1;

    return memcmp(a->prefix, b->prefix, 16);
782 783
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
784 785 786
void
flushupdates(void)
{
787 788 789 790
    struct xroute *xroute;
    struct route *route;
    const unsigned char *last_prefix = NULL;
    unsigned char last_plen = 0xFF;
791
    int i;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
792 793 794 795 796 797 798 799 800

    if(updates > 0) {
        int n = updates;
        struct network *net = update_net;
        updates = 0;
        update_net = NULL;

        debugf("  (flushing %d buffered updates)\n", n);

801 802 803 804 805 806 807 808 809 810 811 812 813 814 815
        /* In order to send fewer update messages, we want to send updates
           with the same router-id together, with IPv6 going out before IPv4. */

        for(i = 0; i < n; i++) {
            route = find_installed_route(buffered_updates[i].prefix,
                                         buffered_updates[i].plen);
            if(route)
                memcpy(buffered_updates[i].id, route->src->id, 16);
            else
                memcpy(buffered_updates[i].id, myid, 16);
        }

        qsort(buffered_updates, n, sizeof(struct buffered_update),
              compare_buffered_updates);

816 817 818
        for(i = 0; i < n; i++) {
            unsigned short seqno;
            unsigned short metric;
819 820 821 822 823 824 825 826 827 828 829

            /* The same update may be scheduled multiple times before it is
               sent out.  Since our buffer is now sorted, it is enough to
               compare with the previous update. */

            if(last_prefix) {
                if(buffered_updates[i].plen == last_plen &&
                   memcmp(buffered_updates[i].prefix, last_prefix, 16) == 0)
                    continue;
            }

830 831
            xroute = find_xroute(buffered_updates[i].prefix,
                                 buffered_updates[i].plen);
832 833 834
            if(xroute) {
                really_send_update(net, myid,
                                   xroute->prefix, xroute->plen,
835
                                   myseqno, xroute->metric);
836 837
                last_prefix = xroute->prefix;
                last_plen = xroute->plen;
838 839 840 841 842 843
                continue;
            }
            route = find_installed_route(buffered_updates[i].prefix,
                                         buffered_updates[i].plen);
            if(route) {
                seqno = route->seqno;
844
                metric = route->metric;
845 846 847 848 849
                if(metric < INFINITY)
                    satisfy_request(route->src->prefix, route->src->plen,
                                    seqno, hash_id(route->src->id), net);
                if(split_horizon && net->wired && route->neigh->network == net)
                    continue;
850
                really_send_update(net, route->src->id,
851 852
                                   route->src->prefix,
                                   route->src->plen,
853
                                   seqno, metric);
854
                update_source(route->src, seqno, metric);
855 856
                last_prefix = route->src->prefix;
                last_plen = route->src->plen;
857
                continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
858 859 860
            }
        }
        schedule_flush_now(net);
861 862
        VALGRIND_MAKE_MEM_UNDEFINED(&buffered_updates,
                                    sizeof(buffered_updates));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
863
    }
864 865
    update_flush_timeout.tv_sec = 0;
    update_flush_timeout.tv_usec = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
866 867 868
}

static void
869
schedule_update_flush(struct network *net, int urgent)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
870
{
871
    int msecs;
872
    msecs = update_jitter(net, urgent);
873 874
    if(update_flush_timeout.tv_sec != 0 &&
       timeval_minus_msec(&update_flush_timeout, &now) < msecs)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
875
        return;
876 877 878
    update_flush_timeout.tv_usec = (now.tv_usec + msecs * 1000) % 1000000;
    update_flush_timeout.tv_sec =
        now.tv_sec + (now.tv_usec / 1000 + msecs) / 1000;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
879 880 881
}

static void
882 883
buffer_update(struct network *net,
              const unsigned char *prefix, unsigned char plen)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
884 885 886 887 888 889 890 891
{
    if(update_net && update_net != net)
        flushupdates();

    update_net = net;

    if(updates >= MAX_BUFFERED_UPDATES)
        flushupdates();
892 893 894
    memcpy(buffered_updates[updates].prefix, prefix, 16);
    buffered_updates[updates].plen = plen;
    updates++;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
895 896 897
}

void
898
send_update(struct network *net, int urgent,
899
            const unsigned char *prefix, unsigned char plen)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
900
{
901
    int i, selfonly;
902
    struct resend *request;
903

904
    if(prefix) {
905
        /* This is needed here, since flushupdates only handles the
906 907 908
           case where network is not null. */
        request = find_request(prefix, plen, NULL);
        if(request) {
909 910
            struct route *route = find_installed_route(prefix, plen);
            if(route && route->metric < INFINITY) {
911 912
                urgent = 1;
                satisfy_request(prefix, plen, route->seqno,
913
                                hash_id(route->src->id), net);
914
            }
915 916
        }
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
917 918

    if(net == NULL) {
919 920 921
        struct network *n;
        FOR_ALL_NETS(n)
            send_update(n, urgent, prefix, plen);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
922 923 924
        return;
    }

925 926 927
    if(!net->up)
        return;

928 929
    selfonly =
        parasitic || (silent_time && now.tv_sec < reboot_time + silent_time);
930

931 932
    if(!selfonly)
        silent_time = 0;
933

934
    if(prefix) {
935 936 937 938 939
        if(!selfonly || find_xroute(prefix, plen)) {
            debugf("Sending update to %s for %s.\n",
                   net->ifname, format_prefix(prefix, plen));
            buffer_update(net, prefix, plen);
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
940
    } else {
941 942 943
        /* Don't send full route dumps more than ten times per second */
        if(net->update_time.tv_sec > 0 &&
           timeval_minus_msec(&now, &net->update_time) < 100)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
944
            return;
945
        send_self_update(net, 0);
946 947 948 949 950 951 952
        if(!selfonly) {
            debugf("Sending update to %s for any.\n", net->ifname);
            for(i = 0; i < numroutes; i++)
                if(routes[i].installed)
                    buffer_update(net,
                                  routes[i].src->prefix, routes[i].src->plen);
        }
953
        delay_jitter(&net->update_time, &net->update_timeout,
954
                     update_interval);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
955
    }
956
    schedule_update_flush(net, urgent);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
957 958
}

959 960 961 962 963 964
void
send_update_resend(struct network *net,
                   const unsigned char *prefix, unsigned char plen)
{
    int delay;

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
965 966
    assert(prefix != NULL);

967 968 969 970 971 972
    send_update(net, 1, prefix, plen);

    delay = 2000;
    delay = MIN(delay, wireless_hello_interval / 2);
    delay = MIN(delay, wired_hello_interval / 2);
    delay = MAX(delay, 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
973
    record_resend(RESEND_UPDATE, prefix, plen, 0, 0, NULL, delay);
974 975 976
}


Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
977
void
978
update_myseqno(int force)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
979
{
980
    if(force || timeval_minus_msec(&now, &seqno_time) >= seqno_interval) {
981
        myseqno = seqno_plus(myseqno, 1);
982
        seqno_time = now;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
983
    }
984 985 986 987 988 989 990 991
}

void
send_self_update(struct network *net, int force_seqno)
{
    int i;

    update_myseqno(force_seqno);
992 993

    if(net == NULL) {
994 995 996
        struct network *n;
        FOR_ALL_NETS(n) {
            if(n->up)
997
                continue;
998
            send_self_update(n, 0);
999
        }
1000 1001 1002 1003 1004
        return;
    }

    debugf("Sending self update to %s.\n", net->ifname);

1005
    delay_jitter(&net->self_update_time, &net->self_update_timeout,
1006
                 net->self_update_interval);
1007
    for(i = 0; i < numxroutes; i++) {
1008
        send_update(net, 0, xroutes[i].prefix, xroutes[i].plen);
1009
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1010 1011 1012
}

void
1013
send_ihu(struct neighbour *neigh, struct network *net)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1014 1015
{
    if(neigh == NULL && net == NULL) {
1016 1017 1018
        struct network *n;
        FOR_ALL_NETS(n) {
            if(n->up)
1019
                continue;
1020
            send_ihu(NULL, n);
1021
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1022 1023 1024 1025
        return;
    }

    if(neigh == NULL) {
1026 1027 1028 1029
        struct neighbour *ngh;
        FOR_ALL_NEIGHBOURS(ngh) {
            if(ngh->network == net)
                send_ihu(ngh, net);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1030 1031
        }
    } else {
1032
        int rxcost, interval;
1033

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1034 1035 1036 1037 1038
        if(net && neigh->network != net)
            return;

        net = neigh->network;

1039 1040
        rxcost = neighbour_rxcost(neigh);

1041
        interval = (net->hello_interval * 3 + 9) / 10;
1042

1043 1044 1045 1046 1047 1048 1049
        /* Conceptually, an IHU is a unicast message.  We usually send
           them as multicast, since this allows aggregation into
           a single packet and avoids an ARP exchange.  If we already
           have a unicast message queued for this neighbour, however,
           we might as well piggyback the IHU onto it. */
        debugf("Sending %sihu %d on %s to %s (%s).\n",
               unicast_neighbour == neigh ? "unicast " : "",
1050
               rxcost,
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1051 1052 1053 1054
               neigh->network->ifname,
               format_address(neigh->id),
               format_address(neigh->address));

1055 1056 1057 1058 1059 1060 1061 1062 1063
        if(unicast_neighbour == neigh) {
            send_unicast_message(neigh, 1, 128, 0,
                                 interval < 0xFFFF ? interval : 0,
                                 rxcost, neigh->id);
        } else {
            send_message(net, 1, 128, 0,
                         interval < 0xFFFF ? interval : 0,
                         rxcost, neigh->id);
        }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1064 1065
    }
}
1066 1067 1068 1069 1070

/* Send IHUs to all marginal neighbours */
void
send_marginal_ihu(struct network *net)
{
1071 1072
    struct neighbour *neigh;
    FOR_ALL_NEIGHBOURS(neigh) {
1073
        if(net && neigh->network != net)
1074
            continue;
1075 1076
        if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000)
            send_ihu(neigh, net);
1077 1078
    }
}