resend.c 8.62 KB
Newer Older
1
/*
2
Copyright (c) 2007, 2008 by Juliusz Chroboczek
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

#include <sys/time.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>

28
#include "babeld.h"
29 30
#include "util.h"
#include "neighbour.h"
31
#include "resend.h"
32
#include "message.h"
33
#include "network.h"
34
#include "configuration.h"
35

36
struct timeval resend_time = {0, 0};
37
struct resend *to_resend = NULL;
38 39

static int
40 41
resend_match(struct resend *resend,
             int kind, const unsigned char *prefix, unsigned char plen)
42
{
43 44
    return (resend->kind == kind &&
            resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
45 46
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
47 48
/* This is called by neigh.c when a neighbour is flushed */

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
49 50 51 52 53 54
void
flush_resends(struct neighbour *neigh)
{
    /* Nothing for now */
}

55 56
static struct resend *
find_resend(int kind, const unsigned char *prefix, unsigned char plen,
57
             struct resend **previous_return)
58
{
59
    struct resend *current, *previous;
60 61

    previous = NULL;
62 63 64
    current = to_resend;
    while(current) {
        if(resend_match(current, kind, prefix, plen)) {
65 66
            if(previous_return)
                *previous_return = previous;
67
            return current;
68
        }
69 70
        previous = current;
        current = current->next;
71 72 73 74 75
    }

    return NULL;
}

76 77 78 79 80 81 82
struct resend *
find_request(const unsigned char *prefix, unsigned char plen,
             struct resend **previous_return)
{
    return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
}

83
int
84
record_resend(int kind, const unsigned char *prefix, unsigned char plen,
85
              unsigned short seqno, const unsigned char *id,
86
              struct network *network, int delay)
87
{
88
    struct resend *resend;
89
    unsigned int ifindex = network ? network->ifindex : 0;
90

91 92 93 94
    if((kind == RESEND_REQUEST &&
        input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) ||
       (kind == RESEND_UPDATE &&
        output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
95 96
        return 0;

97 98 99
    if(delay >= 0xFFFF)
        delay = 0xFFFF;

100 101 102 103
    resend = find_resend(kind, prefix, plen, NULL);
    if(resend) {
        if(resend->delay && delay)
            resend->delay = MIN(resend->delay, delay);
104
        else if(delay)
105 106 107
            resend->delay = delay;
        resend->time = now;
        resend->max = kind == RESEND_REQUEST ? 128 : UPDATE_MAX;
108
        if(id && memcmp(resend->id, id, 8) == 0 &&
109
           seqno_compare(resend->seqno, seqno) > 0) {
110 111
            return 0;
        }
112 113 114 115
        if(id)
            memcpy(resend->id, id, 8);
        else
            memset(resend->id, 0, 8);
116 117 118
        resend->seqno = seqno;
        if(resend->network != network)
            resend->network = NULL;
119
    } else {
120 121
        resend = malloc(sizeof(struct resend));
        if(resend == NULL)
122
            return -1;
123 124 125 126 127 128
        resend->kind = kind;
        resend->max = kind == RESEND_REQUEST ? 128 : UPDATE_MAX;
        resend->delay = delay;
        memcpy(resend->prefix, prefix, 16);
        resend->plen = plen;
        resend->seqno = seqno;
129 130 131 132
        if(id)
            memcpy(resend->id, id, 8);
        else
            memset(resend->id, 0, 8);
133 134 135 136
        resend->network = network;
        resend->time = now;
        resend->next = to_resend;
        to_resend = resend;
137
    }
138

139
    if(resend->delay) {
140
        struct timeval timeout;
141
        timeval_add_msec(&timeout, &resend->time, resend->delay);
142
        timeval_min(&resend_time, &timeout);
143 144
    }
    return 1;
145 146
}

147 148 149 150 151 152 153 154 155 156 157
static int
resend_expired(struct resend *resend)
{
    switch(resend->kind) {
    case RESEND_REQUEST:
        return timeval_minus_msec(&now, &resend->time) >= REQUEST_TIMEOUT;
    default:
        return resend->max <= 0;
    }
}

158 159
int
unsatisfied_request(const unsigned char *prefix, unsigned char plen,
160
                    unsigned short seqno, const unsigned char *id)
161
{
162
    struct resend *request;
163 164

    request = find_request(prefix, plen, NULL);
165
    if(request == NULL || resend_expired(request))
166 167
        return 0;

168
    if(memcmp(request->id, id, 8) != 0 ||
169 170 171 172 173 174
       seqno_compare(request->seqno, seqno) <= 0)
        return 1;

    return 0;
}

175 176 177 178
/* Determine whether a given request should be forwarded. */
int
request_redundant(struct network *net,
                  const unsigned char *prefix, unsigned char plen,
179
                  unsigned short seqno, const unsigned char *id)
180 181 182 183 184 185 186
{
    struct resend *request;

    request = find_request(prefix, plen, NULL);
    if(request == NULL || resend_expired(request))
        return 0;

187
    if(memcmp(request->id, id, 8) == 0 &&
188 189 190 191 192 193 194 195 196 197 198
       seqno_compare(request->seqno, seqno) > 0)
        return 0;

    if(request->network != NULL && request->network != net)
        return 0;

    if(request->max > 0)
        /* Will be resent. */
        return 1;

    if(timeval_minus_msec(&now, &request->time) <
199
       (net ? MIN(net->hello_interval, 1000) : 1000))
200 201 202 203 204 205
        /* Fairly recent. */
        return 1;

    return 0;
}

206 207
int
satisfy_request(const unsigned char *prefix, unsigned char plen,
208
                unsigned short seqno, const unsigned char *id,
209 210
                struct network *network)
{
211
    struct resend *request, *previous;
212 213 214 215 216 217 218 219

    request = find_request(prefix, plen, &previous);
    if(request == NULL)
        return 0;

    if(network != NULL && request->network != network)
        return 0;

220
    if(memcmp(request->id, id, 8) != 0 ||
221
       seqno_compare(request->seqno, seqno) <= 0) {
222 223 224 225
        /* We cannot remove the request, as we may be walking the list right
           now.  Mark it as expired, so that expire_resend will remove it. */
        request->max = 0;
        request->time.tv_sec = 0;
226
        recompute_resend_time();
227 228 229 230 231 232 233
        return 1;
    }

    return 0;
}

void
234
expire_resend()
235
{
236
    struct resend *current, *previous;
237
    int recompute = 0;
238 239

    previous = NULL;
240 241 242
    current = to_resend;
    while(current) {
        if(resend_expired(current)) {
243
            if(previous == NULL) {
244 245 246
                to_resend = current->next;
                free(current);
                current = to_resend;
247
            } else {
248 249 250
                previous->next = current->next;
                free(current);
                current = previous->next;
251
            }
252
            recompute = 1;
253
        } else {
254
            current = current->next;
255 256
        }
    }
257
    if(recompute)
258
        recompute_resend_time();
259 260
}

261
void
262
recompute_resend_time()
263
{
264
    struct resend *request;
265
    struct timeval resend = {0, 0};
266

267
    request = to_resend;
268
    while(request) {
269
        if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
270
            struct timeval timeout;
271
            timeval_add_msec(&timeout, &request->time, request->delay);
272
            timeval_min(&resend, &timeout);
273
        }
274 275 276
        request = request->next;
    }

277
    resend_time = resend;
278 279 280
}

void
281
do_resend()
282
{
283
    struct resend *resend;
284

285 286 287
    resend = to_resend;
    while(resend) {
        if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
288
            struct timeval timeout;
289
            timeval_add_msec(&timeout, &resend->time, resend->delay);
290
            if(timeval_compare(&now, &timeout) >= 0) {
291 292
                switch(resend->kind) {
                case RESEND_REQUEST:
293 294 295
                    send_multihop_request(resend->network,
                                          resend->prefix, resend->plen,
                                          resend->seqno, resend->id, 127);
296 297 298 299 300 301 302
                    break;
                case RESEND_UPDATE:
                    send_update(resend->network, 1,
                                resend->prefix, resend->plen);
                    break;
                default: abort();
                }
303
                resend->delay = MIN(0xFFFF, resend->delay * 2);
304
                resend->max--;
305
            }
306
        }
307
        resend = resend->next;
308
    }
309
    recompute_resend_time();
310
}