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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to resend.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / babeld