babeld/neighbour.c

   1 // SPDX-License-Identifier: MIT
   2 /*
   3 Copyright (c) 2007, 2008 by Juliusz Chroboczek
   4 */
   5
   6 #ifdef HAVE_CONFIG_H
   7 #include "config.h"
   8 #endif
   9
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <stdio.h>
  13 #include <sys/time.h>
  14 #include <time.h>
  15
  16 #include <zebra.h>
  17 #include "if.h"
  18
  19 #include "babel_main.h"
  20 #include "babeld.h"
  21 #include "util.h"
  22 #include "babel_interface.h"
  23 #include "neighbour.h"
  24 #include "source.h"
  25 #include "route.h"
  26 #include "message.h"
  27 #include "resend.h"
  28 #include "babel_errors.h"
  29
  30 struct neighbour *neighs = NULL;
  31
  32 static struct neighbour *
  33 find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
  34 {
  35     struct neighbour *neigh;
  36     FOR_ALL_NEIGHBOURS(neigh) {
  37         if(memcmp(address, neigh->address, 16) == 0 &&
  38            neigh->ifp == ifp)
  39             return neigh;
  40     }
  41     return NULL;
  42 }
  43
  44 void
  45 flush_neighbour(struct neighbour *neigh)
  46 {
  47     debugf(BABEL_DEBUG_COMMON,"Flushing neighbour %s (reach 0x%04x)",
  48            format_address(neigh->address), neigh->reach);
  49     flush_neighbour_routes(neigh);
  50     if(unicast_neighbour == neigh)
  51         flush_unicast(1);
  52     flush_resends(neigh);
  53
  54     if(neighs == neigh) {
  55         neighs = neigh->next;
  56     } else {
  57         struct neighbour *previous = neighs;
  58         while(previous->next != neigh)
  59             previous = previous->next;
  60         previous->next = neigh->next;
  61     }
  62     free(neigh);
  63 }
  64
  65 struct neighbour *
  66 find_neighbour(const unsigned char *address, struct interface *ifp)
  67 {
  68     struct neighbour *neigh;
  69     const struct timeval zero = {0, 0};
  70
  71     neigh = find_neighbour_nocreate(address, ifp);
  72     if(neigh)
  73         return neigh;
  74
  75     debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
  76            format_address(address), ifp->name);
  77
  78     neigh = malloc(sizeof(struct neighbour));
  79     if(neigh == NULL) {
  80         flog_err(EC_BABEL_MEMORY, "malloc(neighbour): %s",
  81                   safe_strerror(errno));
  82         return NULL;
  83     }
  84
  85     neigh->hello_seqno = -1;
  86     memcpy(neigh->address, address, 16);
  87     neigh->reach = 0;
  88     neigh->txcost = INFINITY;
  89     neigh->ihu_time = babel_now;
  90     neigh->hello_time = zero;
  91     neigh->hello_interval = 0;
  92     neigh->ihu_interval = 0;
  93     neigh->hello_send_us = 0;
  94     neigh->hello_rtt_receive_time = zero;
  95     neigh->rtt = 0;
  96     neigh->rtt_time = zero;
  97     neigh->ifp = ifp;
  98     neigh->next = neighs;
  99     neighs = neigh;
 100     send_hello(ifp);
 101     return neigh;
 102 }
 103
 104 /* Recompute a neighbour's rxcost.  Return true if anything changed. */
 105 int
 106 update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
 107 {
 108     int missed_hellos;
 109     int rc = 0;
 110
 111     if(hello < 0) {
 112         if(neigh->hello_interval == 0)
 113             return rc;
 114         missed_hellos =
 115             ((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
 116              neigh->hello_interval * 7) /
 117             (neigh->hello_interval * 10);
 118         if(missed_hellos <= 0)
 119             return rc;
 120         timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
 121                           missed_hellos * neigh->hello_interval * 10);
 122     } else {
 123         if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
 124             missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
 125             if(missed_hellos < -8) {
 126                 /* Probably a neighbour that rebooted and lost its seqno.
 127                    Reboot the universe. */
 128                 neigh->reach = 0;
 129                 missed_hellos = 0;
 130                 rc = 1;
 131             } else if(missed_hellos < 0) {
 132                 if(hello_interval > neigh->hello_interval) {
 133                     /* This neighbour has increased its hello interval,
 134                        and we didn't notice. */
 135                     neigh->reach <<= -missed_hellos;
 136                     missed_hellos = 0;
 137                 } else {
 138                     /* Late hello.  Probably due to the link layer buffering
 139                        packets during a link outage.  Ignore it, but reset
 140                        the expected seqno. */
 141                     neigh->hello_seqno = hello;
 142                     hello = -1;
 143                     missed_hellos = 0;
 144                 }
 145                 rc = 1;
 146             }
 147         } else {
 148             missed_hellos = 0;
 149         }
 150         neigh->hello_time = babel_now;
 151         neigh->hello_interval = hello_interval;
 152     }
 153
 154     if(missed_hellos > 0) {
 155         neigh->reach >>= missed_hellos;
 156         neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
 157         rc = 1;
 158     }
 159
 160     if(hello >= 0) {
 161         neigh->hello_seqno = hello;
 162         neigh->reach >>= 1;
 163         neigh->reach |= 0x8000;
 164         if((neigh->reach & 0xFC00) != 0xFC00)
 165             rc = 1;
 166     }
 167
 168     /* Make sure to give neighbours some feedback early after association */
 169     if((neigh->reach & 0xBF00) == 0x8000) {
 170         /* A new neighbour */
 171         send_hello(neigh->ifp);
 172     } else {
 173         /* Don't send hellos, in order to avoid a positive feedback loop. */
 174         int a = (neigh->reach & 0xC000);
 175         int b = (neigh->reach & 0x3000);
 176         if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
 177             /* Reachability is either 1100 or 0011 */
 178             send_self_update(neigh->ifp);
 179         }
 180     }
 181
 182     if((neigh->reach & 0xFC00) == 0xC000) {
 183         /* This is a newish neighbour, let's request a full route dump.
 184            We ought to avoid this when the network is dense */
 185         send_unicast_request(neigh, NULL, 0);
 186         send_ihu(neigh, NULL);
 187     }
 188     return rc;
 189 }
 190
 191 static int
 192 reset_txcost(struct neighbour *neigh)
 193 {
 194     unsigned delay;
 195
 196     delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
 197
 198     if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
 199         return 0;
 200
 201     /* If we're losing a lot of packets, we probably lost an IHU too */
 202     if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
 203        (neigh->ihu_interval > 0 &&
 204         delay >= neigh->ihu_interval * 10U * 10U)) {
 205         neigh->txcost = INFINITY;
 206         neigh->ihu_time = babel_now;
 207         return 1;
 208     }
 209
 210     return 0;
 211 }
 212
 213 unsigned
 214 neighbour_txcost(struct neighbour *neigh)
 215 {
 216     return neigh->txcost;
 217 }
 218
 219 unsigned
 220 check_neighbours(void)
 221 {
 222     struct neighbour *neigh;
 223     int changed, rc;
 224     unsigned msecs = 50000;
 225
 226     debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
 227
 228     neigh = neighs;
 229     while(neigh) {
 230         changed = update_neighbour(neigh, -1, 0);
 231
 232         if(neigh->reach == 0 ||
 233            neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
 234            timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
 235             struct neighbour *old = neigh;
 236             neigh = neigh->next;
 237             flush_neighbour(old);
 238             continue;
 239         }
 240
 241         rc = reset_txcost(neigh);
 242         changed = changed || rc;
 243
 244         update_neighbour_metric(neigh, changed);
 245
 246         if(neigh->hello_interval > 0)
 247             msecs = MIN(msecs, neigh->hello_interval * 10U);
 248         if(neigh->ihu_interval > 0)
 249             msecs = MIN(msecs, neigh->ihu_interval * 10U);
 250         neigh = neigh->next;
 251     }
 252
 253     return msecs;
 254 }
 255
 256 unsigned
 257 neighbour_rxcost(struct neighbour *neigh)
 258 {
 259     unsigned delay;
 260     unsigned short reach = neigh->reach;
 261
 262     delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
 263
 264     if((reach & 0xFFF0) == 0 || delay >= 180000) {
 265         return INFINITY;
 266     } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
 267         int sreach =
 268             ((reach & 0x8000) >> 2) +
 269             ((reach & 0x4000) >> 1) +
 270             (reach & 0x3FFF);
 271         /* 0 <= sreach <= 0x7FFF */
 272         int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
 273         /* cost >= interface->cost */
 274         if(delay >= 40000)
 275             cost = (cost * (delay - 20000) + 10000) / 20000;
 276         return MIN(cost, INFINITY);
 277     } else {
 278         /* To lose one hello is a misfortune, to lose two is carelessness. */
 279         if((reach & 0xC000) == 0xC000)
 280             return babel_get_if_nfo(neigh->ifp)->cost;
 281         else if((reach & 0xC000) == 0)
 282             return INFINITY;
 283         else if((reach & 0x2000))
 284             return babel_get_if_nfo(neigh->ifp)->cost;
 285         else
 286             return INFINITY;
 287     }
 288 }
 289
 290 unsigned
 291 neighbour_rttcost(struct neighbour *neigh)
 292 {
 293     struct interface *ifp = neigh->ifp;
 294     babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
 295
 296     if(!babel_ifp->max_rtt_penalty || !valid_rtt(neigh))
 297         return 0;
 298
 299     /* Function: linear behaviour between rtt_min and rtt_max. */
 300     if(neigh->rtt <= babel_ifp->rtt_min) {
 301         return 0;
 302     } else if(neigh->rtt <= babel_ifp->rtt_max) {
 303         unsigned long long tmp =
 304             (unsigned long long)babel_ifp->max_rtt_penalty *
 305             (neigh->rtt - babel_ifp->rtt_min) /
 306             (babel_ifp->rtt_max - babel_ifp->rtt_min);
 307         assert((tmp & 0x7FFFFFFF) == tmp);
 308         return tmp;
 309     } else {
 310         return babel_ifp->max_rtt_penalty;
 311     }
 312 }
 313
 314 unsigned
 315 neighbour_cost(struct neighbour *neigh)
 316 {
 317     unsigned a, b, cost;
 318
 319     if(!if_up(neigh->ifp))
 320         return INFINITY;
 321
 322     a = neighbour_txcost(neigh);
 323
 324     if(a >= INFINITY)
 325         return INFINITY;
 326
 327     b = neighbour_rxcost(neigh);
 328     if(b >= INFINITY)
 329         return INFINITY;
 330
 331     if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
 332        || (a < 256 && b < 256)) {
 333         cost = a;
 334     } else {
 335         /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
 336            probabilities of a packet getting through in the direct and reverse
 337            directions. */
 338         a = MAX(a, 256);
 339         b = MAX(b, 256);
 340         /* 1/(alpha * beta), which is just plain ETX. */
 341         /* Since a and b are capped to 16 bits, overflow is impossible. */
 342         cost = (a * b + 128) >> 8;
 343     }
 344
 345     cost += neighbour_rttcost(neigh);
 346
 347     return MIN(cost, INFINITY);
 348 }
 349
 350 int
 351 valid_rtt(struct neighbour *neigh)
 352 {
 353     return (timeval_minus_msec(&babel_now, &neigh->rtt_time) < 180000) ? 1 : 0;
 354 }