]>
Commit | Line | Data |
---|---|---|
ca10883e DS |
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 | ||
b45ac5f5 DL |
23 | #ifdef HAVE_CONFIG_H |
24 | #include "config.h" | |
25 | #endif | |
26 | ||
ca10883e DS |
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 | |
4d762f26 | 241 | expire_resend(void) |
ca10883e DS |
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 | |
4d762f26 | 270 | recompute_resend_time(void) |
ca10883e DS |
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 | |
4d762f26 | 289 | do_resend(void) |
ca10883e DS |
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 | } |