babeld/resend.c

   1 /*
   2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to deal
   6 in the Software without restriction, including without limitation the rights
   7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8 copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20 THE SOFTWARE.
  21 */
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include "config.h"
  25 #endif
  26
  27 #include <sys/time.h>
  28 #include <time.h>
  29 #include <string.h>
  30 #include <stdlib.h>
  31
  32 #include <zebra.h>
  33 #include "if.h"
  34
  35 #include "babel_main.h"
  36 #include "babeld.h"
  37 #include "util.h"
  38 #include "neighbour.h"
  39 #include "resend.h"
  40 #include "message.h"
  41 #include "babel_interface.h"
  42
  43 struct timeval resend_time = {0, 0};
  44 struct resend *to_resend = NULL;
  45
  46 static int
  47 resend_match(struct resend *resend,
  48              int kind, const unsigned char *prefix, unsigned char plen)
  49 {
  50     return (resend->kind == kind &&
  51             resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
  52 }
  53
  54 /* This is called by neigh.c when a neighbour is flushed */
  55
  56 void
  57 flush_resends(struct neighbour *neigh)
  58 {
  59     /* Nothing for now */
  60 }
  61
  62 static struct resend *
  63 find_resend(int kind, const unsigned char *prefix, unsigned char plen,
  64              struct resend **previous_return)
  65 {
  66     struct resend *current, *previous;
  67
  68     previous = NULL;
  69     current = to_resend;
  70     while(current) {
  71         if(resend_match(current, kind, prefix, plen)) {
  72             if(previous_return)
  73                 *previous_return = previous;
  74             return current;
  75         }
  76         previous = current;
  77         current = current->next;
  78     }
  79
  80     return NULL;
  81 }
  82
  83 struct resend *
  84 find_request(const unsigned char *prefix, unsigned char plen,
  85              struct resend **previous_return)
  86 {
  87     return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
  88 }
  89
  90 int
  91 record_resend(int kind, const unsigned char *prefix, unsigned char plen,
  92               unsigned short seqno, const unsigned char *id,
  93               struct interface *ifp, int delay)
  94 {
  95     struct resend *resend;
  96     unsigned int ifindex = ifp ? ifp->ifindex : 0;
  97
  98     if((kind == RESEND_REQUEST &&
  99         input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) ||
 100        (kind == RESEND_UPDATE &&
 101         output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
 102         return 0;
 103
 104     if(delay >= 0xFFFF)
 105         delay = 0xFFFF;
 106
 107     resend = find_resend(kind, prefix, plen, NULL);
 108     if(resend) {
 109         if(resend->delay && delay)
 110             resend->delay = MIN(resend->delay, delay);
 111         else if(delay)
 112             resend->delay = delay;
 113         resend->time = babel_now;
 114         resend->max = RESEND_MAX;
 115         if(id && memcmp(resend->id, id, 8) == 0 &&
 116            seqno_compare(resend->seqno, seqno) > 0) {
 117             return 0;
 118         }
 119         if(id)
 120             memcpy(resend->id, id, 8);
 121         else
 122             memset(resend->id, 0, 8);
 123         resend->seqno = seqno;
 124         if(resend->ifp != ifp)
 125             resend->ifp = NULL;
 126     } else {
 127         resend = malloc(sizeof(struct resend));
 128         if(resend == NULL)
 129             return -1;
 130         resend->kind = kind;
 131         resend->max = RESEND_MAX;
 132         resend->delay = delay;
 133         memcpy(resend->prefix, prefix, 16);
 134         resend->plen = plen;
 135         resend->seqno = seqno;
 136         if(id)
 137             memcpy(resend->id, id, 8);
 138         else
 139             memset(resend->id, 0, 8);
 140         resend->ifp = ifp;
 141         resend->time = babel_now;
 142         resend->next = to_resend;
 143         to_resend = resend;
 144     }
 145
 146     if(resend->delay) {
 147         struct timeval timeout;
 148         timeval_add_msec(&timeout, &resend->time, resend->delay);
 149         timeval_min(&resend_time, &timeout);
 150     }
 151     return 1;
 152 }
 153
 154 static int
 155 resend_expired(struct resend *resend)
 156 {
 157     switch(resend->kind) {
 158     case RESEND_REQUEST:
 159         return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT;
 160     default:
 161         return resend->max <= 0;
 162     }
 163 }
 164
 165 int
 166 unsatisfied_request(const unsigned char *prefix, unsigned char plen,
 167                     unsigned short seqno, const unsigned char *id)
 168 {
 169     struct resend *request;
 170
 171     request = find_request(prefix, plen, NULL);
 172     if(request == NULL || resend_expired(request))
 173         return 0;
 174
 175     if(memcmp(request->id, id, 8) != 0 ||
 176        seqno_compare(request->seqno, seqno) <= 0)
 177         return 1;
 178
 179     return 0;
 180 }
 181
 182 /* Determine whether a given request should be forwarded. */
 183 int
 184 request_redundant(struct interface *ifp,
 185                   const unsigned char *prefix, unsigned char plen,
 186                   unsigned short seqno, const unsigned char *id)
 187 {
 188     struct resend *request;
 189
 190     request = find_request(prefix, plen, NULL);
 191     if(request == NULL || resend_expired(request))
 192         return 0;
 193
 194     if(memcmp(request->id, id, 8) == 0 &&
 195        seqno_compare(request->seqno, seqno) > 0)
 196         return 0;
 197
 198     if(request->ifp != NULL && request->ifp != ifp)
 199         return 0;
 200
 201     if(request->max > 0)
 202         /* Will be resent. */
 203         return 1;
 204
 205     if(timeval_minus_msec(&babel_now, &request->time) <
 206        (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000))
 207         /* Fairly recent. */
 208         return 1;
 209
 210     return 0;
 211 }
 212
 213 int
 214 satisfy_request(const unsigned char *prefix, unsigned char plen,
 215                 unsigned short seqno, const unsigned char *id,
 216                 struct interface *ifp)
 217 {
 218     struct resend *request, *previous;
 219
 220     request = find_request(prefix, plen, &previous);
 221     if(request == NULL)
 222         return 0;
 223
 224     if(ifp != NULL && request->ifp != ifp)
 225         return 0;
 226
 227     if(memcmp(request->id, id, 8) != 0 ||
 228        seqno_compare(request->seqno, seqno) <= 0) {
 229         /* We cannot remove the request, as we may be walking the list right
 230            now.  Mark it as expired, so that expire_resend will remove it. */
 231         request->max = 0;
 232         request->time.tv_sec = 0;
 233         recompute_resend_time();
 234         return 1;
 235     }
 236
 237     return 0;
 238 }
 239
 240 void
 241 expire_resend(void)
 242 {
 243     struct resend *current, *previous;
 244     int recompute = 0;
 245
 246     previous = NULL;
 247     current = to_resend;
 248     while(current) {
 249         if(resend_expired(current)) {
 250             if(previous == NULL) {
 251                 to_resend = current->next;
 252                 free(current);
 253                 current = to_resend;
 254             } else {
 255                 previous->next = current->next;
 256                 free(current);
 257                 current = previous->next;
 258             }
 259             recompute = 1;
 260         } else {
 261             previous = current;
 262             current = current->next;
 263         }
 264     }
 265     if(recompute)
 266         recompute_resend_time();
 267 }
 268
 269 void
 270 recompute_resend_time(void)
 271 {
 272     struct resend *request;
 273     struct timeval resend = {0, 0};
 274
 275     request = to_resend;
 276     while(request) {
 277         if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
 278             struct timeval timeout;
 279             timeval_add_msec(&timeout, &request->time, request->delay);
 280             timeval_min(&resend, &timeout);
 281         }
 282         request = request->next;
 283     }
 284
 285     resend_time = resend;
 286 }
 287
 288 void
 289 do_resend(void)
 290 {
 291     struct resend *resend;
 292
 293     resend = to_resend;
 294     while(resend) {
 295         if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
 296             struct timeval timeout;
 297             timeval_add_msec(&timeout, &resend->time, resend->delay);
 298             if(timeval_compare(&babel_now, &timeout) >= 0) {
 299                 switch(resend->kind) {
 300                 case RESEND_REQUEST:
 301                     send_multihop_request(resend->ifp,
 302                                           resend->prefix, resend->plen,
 303                                           resend->seqno, resend->id, 127);
 304                     break;
 305                 case RESEND_UPDATE:
 306                     send_update(resend->ifp, 1,
 307                                 resend->prefix, resend->plen);
 308                     break;
 309                 default: abort();
 310                 }
 311                 resend->delay = MIN(0xFFFF, resend->delay * 2);
 312                 resend->max--;
 313             }
 314         }
 315         resend = resend->next;
 316     }
 317     recompute_resend_time();
 318 }