babeld/resend.c

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