babeld/resend.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 <sys/time.h>
  11 #include <time.h>
  12 #include <string.h>
  13 #include <stdlib.h>
  14
  15 #include <zebra.h>
  16 #include "if.h"
  17
  18 #include "babel_main.h"
  19 #include "babeld.h"
  20 #include "util.h"
  21 #include "neighbour.h"
  22 #include "resend.h"
  23 #include "message.h"
  24 #include "babel_interface.h"
  25
  26 struct timeval resend_time = {0, 0};
  27 struct resend *to_resend = NULL;
  28
  29 static int
  30 resend_match(struct resend *resend,
  31              int kind, const unsigned char *prefix, unsigned char plen)
  32 {
  33     return (resend->kind == kind &&
  34             resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
  35 }
  36
  37 /* This is called by neigh.c when a neighbour is flushed */
  38
  39 void
  40 flush_resends(struct neighbour *neigh)
  41 {
  42     /* Nothing for now */
  43 }
  44
  45 static struct resend *
  46 find_resend(int kind, const unsigned char *prefix, unsigned char plen,
  47              struct resend **previous_return)
  48 {
  49     struct resend *current, *previous;
  50
  51     previous = NULL;
  52     current = to_resend;
  53     while(current) {
  54         if(resend_match(current, kind, prefix, plen)) {
  55             if(previous_return)
  56                 *previous_return = previous;
  57             return current;
  58         }
  59         previous = current;
  60         current = current->next;
  61     }
  62
  63     return NULL;
  64 }
  65
  66 struct resend *
  67 find_request(const unsigned char *prefix, unsigned char plen,
  68              struct resend **previous_return)
  69 {
  70     return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
  71 }
  72
  73 int
  74 record_resend(int kind, const unsigned char *prefix, unsigned char plen,
  75               unsigned short seqno, const unsigned char *id,
  76               struct interface *ifp, int delay)
  77 {
  78     struct resend *resend;
  79     unsigned int ifindex = ifp ? ifp->ifindex : 0;
  80
  81     if((kind == RESEND_REQUEST &&
  82         input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) ||
  83        (kind == RESEND_UPDATE &&
  84         output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
  85         return 0;
  86
  87     if(delay >= 0xFFFF)
  88         delay = 0xFFFF;
  89
  90     resend = find_resend(kind, prefix, plen, NULL);
  91     if(resend) {
  92         if(resend->delay && delay)
  93             resend->delay = MIN(resend->delay, delay);
  94         else if(delay)
  95             resend->delay = delay;
  96         resend->time = babel_now;
  97         resend->max = RESEND_MAX;
  98         if(id && memcmp(resend->id, id, 8) == 0 &&
  99            seqno_compare(resend->seqno, seqno) > 0) {
 100             return 0;
 101         }
 102         if(id)
 103             memcpy(resend->id, id, 8);
 104         else
 105             memset(resend->id, 0, 8);
 106         resend->seqno = seqno;
 107         if(resend->ifp != ifp)
 108             resend->ifp = NULL;
 109     } else {
 110         resend = malloc(sizeof(struct resend));
 111         if(resend == NULL)
 112             return -1;
 113         resend->kind = kind;
 114         resend->max = RESEND_MAX;
 115         resend->delay = delay;
 116         memcpy(resend->prefix, prefix, 16);
 117         resend->plen = plen;
 118         resend->seqno = seqno;
 119         if(id)
 120             memcpy(resend->id, id, 8);
 121         else
 122             memset(resend->id, 0, 8);
 123         resend->ifp = ifp;
 124         resend->time = babel_now;
 125         resend->next = to_resend;
 126         to_resend = resend;
 127     }
 128
 129     if(resend->delay) {
 130         struct timeval timeout;
 131         timeval_add_msec(&timeout, &resend->time, resend->delay);
 132         timeval_min(&resend_time, &timeout);
 133     }
 134     return 1;
 135 }
 136
 137 static int
 138 resend_expired(struct resend *resend)
 139 {
 140     switch(resend->kind) {
 141     case RESEND_REQUEST:
 142         return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT;
 143     default:
 144         return resend->max <= 0;
 145     }
 146 }
 147
 148 int
 149 unsatisfied_request(const unsigned char *prefix, unsigned char plen,
 150                     unsigned short seqno, const unsigned char *id)
 151 {
 152     struct resend *request;
 153
 154     request = find_request(prefix, plen, NULL);
 155     if(request == NULL || resend_expired(request))
 156         return 0;
 157
 158     if(memcmp(request->id, id, 8) != 0 ||
 159        seqno_compare(request->seqno, seqno) <= 0)
 160         return 1;
 161
 162     return 0;
 163 }
 164
 165 /* Determine whether a given request should be forwarded. */
 166 int
 167 request_redundant(struct interface *ifp,
 168                   const unsigned char *prefix, unsigned char plen,
 169                   unsigned short seqno, const unsigned char *id)
 170 {
 171     struct resend *request;
 172
 173     request = find_request(prefix, plen, NULL);
 174     if(request == NULL || resend_expired(request))
 175         return 0;
 176
 177     if(memcmp(request->id, id, 8) == 0 &&
 178        seqno_compare(request->seqno, seqno) > 0)
 179         return 0;
 180
 181     if(request->ifp != NULL && request->ifp != ifp)
 182         return 0;
 183
 184     if(request->max > 0)
 185         /* Will be resent. */
 186         return 1;
 187
 188     if(timeval_minus_msec(&babel_now, &request->time) <
 189        (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000))
 190         /* Fairly recent. */
 191         return 1;
 192
 193     return 0;
 194 }
 195
 196 int
 197 satisfy_request(const unsigned char *prefix, unsigned char plen,
 198                 unsigned short seqno, const unsigned char *id,
 199                 struct interface *ifp)
 200 {
 201     struct resend *request, *previous;
 202
 203     request = find_request(prefix, plen, &previous);
 204     if(request == NULL)
 205         return 0;
 206
 207     if(ifp != NULL && request->ifp != ifp)
 208         return 0;
 209
 210     if(memcmp(request->id, id, 8) != 0 ||
 211        seqno_compare(request->seqno, seqno) <= 0) {
 212         /* We cannot remove the request, as we may be walking the list right
 213            now.  Mark it as expired, so that expire_resend will remove it. */
 214         request->max = 0;
 215         request->time.tv_sec = 0;
 216         recompute_resend_time();
 217         return 1;
 218     }
 219
 220     return 0;
 221 }
 222
 223 void
 224 expire_resend(void)
 225 {
 226     struct resend *current, *previous;
 227     int recompute = 0;
 228
 229     previous = NULL;
 230     current = to_resend;
 231     while(current) {
 232         if(resend_expired(current)) {
 233             if(previous == NULL) {
 234                 to_resend = current->next;
 235                 free(current);
 236                 current = to_resend;
 237             } else {
 238                 previous->next = current->next;
 239                 free(current);
 240                 current = previous->next;
 241             }
 242             recompute = 1;
 243         } else {
 244             previous = current;
 245             current = current->next;
 246         }
 247     }
 248     if(recompute)
 249         recompute_resend_time();
 250 }
 251
 252 void
 253 recompute_resend_time(void)
 254 {
 255     struct resend *request;
 256     struct timeval resend = {0, 0};
 257
 258     request = to_resend;
 259     while(request) {
 260         if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
 261             struct timeval timeout;
 262             timeval_add_msec(&timeout, &request->time, request->delay);
 263             timeval_min(&resend, &timeout);
 264         }
 265         request = request->next;
 266     }
 267
 268     resend_time = resend;
 269 }
 270
 271 void
 272 do_resend(void)
 273 {
 274     struct resend *resend;
 275
 276     resend = to_resend;
 277     while(resend) {
 278         if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
 279             struct timeval timeout;
 280             timeval_add_msec(&timeout, &resend->time, resend->delay);
 281             if(timeval_compare(&babel_now, &timeout) >= 0) {
 282                 switch(resend->kind) {
 283                 case RESEND_REQUEST:
 284                     send_multihop_request(resend->ifp,
 285                                           resend->prefix, resend->plen,
 286                                           resend->seqno, resend->id, 127);
 287                     break;
 288                 case RESEND_UPDATE:
 289                     send_update(resend->ifp, 1,
 290                                 resend->prefix, resend->plen);
 291                     break;
 292                 default: abort();
 293                 }
 294                 resend->delay = MIN(0xFFFF, resend->delay * 2);
 295                 resend->max--;
 296             }
 297         }
 298         resend = resend->next;
 299     }
 300     recompute_resend_time();
 301 }