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