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 *
18Copyright (c) 2007, 2008 by Juliusz Chroboczek
19
20Permission is hereby granted, free of charge, to any person obtaining a copy
21of this software and associated documentation files (the "Software"), to deal
22in the Software without restriction, including without limitation the rights
23to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
24copies of the Software, and to permit persons to whom the Software is
25furnished to do so, subject to the following conditions:
26
27The above copyright notice and this permission notice shall be included in
28all copies or substantial portions of the Software.
29
30THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
31IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
32FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
33AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
34LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
35OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
36THE 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
55struct timeval resend_time = {0, 0};
56struct resend *to_resend = NULL;
57
58static int
59resend_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
68void
69flush_resends(struct neighbour *neigh)
70{
71    /* Nothing for now */
72}
73
74static struct resend *
75find_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
95struct resend *
96find_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
102int
103record_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
166static int
167resend_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
177int
178unsatisfied_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. */
195int
196request_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
225int
226satisfy_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
252void
253expire_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
281void
282recompute_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
300void
301do_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}
331