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
23 #include <stdlib.h>
24 #include <string.h>
25 #include <stdio.h>
26 #include <sys/time.h>
27 #include <sys/socket.h>
28 #include <netinet/in.h>
29 #include <time.h>
30 #include <assert.h>
31
32 #include "babeld.h"
33 #include "util.h"
34 #include "interface.h"
35 #include "neighbour.h"
36 #include "source.h"
37 #include "route.h"
38 #include "message.h"
39 #include "resend.h"
40 #include "local.h"
41
42 struct neighbour *neighs = NULL;
43
44 static struct neighbour *
find_neighbour_nocreate(const unsigned char * address,struct interface * ifp)45 find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
46 {
47 struct neighbour *neigh;
48 FOR_ALL_NEIGHBOURS(neigh) {
49 if(memcmp(address, neigh->address, 16) == 0 &&
50 neigh->ifp == ifp)
51 return neigh;
52 }
53 return NULL;
54 }
55
56 void
flush_neighbour(struct neighbour * neigh)57 flush_neighbour(struct neighbour *neigh)
58 {
59 flush_neighbour_routes(neigh);
60 flush_resends(neigh);
61
62 if(neighs == neigh) {
63 neighs = neigh->next;
64 } else {
65 struct neighbour *previous = neighs;
66 while(previous->next != neigh)
67 previous = previous->next;
68 previous->next = neigh->next;
69 }
70 local_notify_neighbour(neigh, LOCAL_FLUSH);
71 free(neigh->buf.buf);
72 free(neigh);
73 }
74
75 struct neighbour *
find_neighbour(const unsigned char * address,struct interface * ifp)76 find_neighbour(const unsigned char *address, struct interface *ifp)
77 {
78 struct neighbour *neigh;
79 const struct timeval zero = {0, 0};
80 unsigned char *buf;
81
82 neigh = find_neighbour_nocreate(address, ifp);
83 if(neigh)
84 return neigh;
85
86 debugf("Creating neighbour %s on %s.\n",
87 format_address(address), ifp->name);
88
89 buf = malloc(ifp->buf.size);
90 if(buf == NULL) {
91 perror("malloc(neighbour->buf)");
92 return NULL;
93 }
94
95 neigh = calloc(1, sizeof(struct neighbour));
96 if(neigh == NULL) {
97 free(buf);
98 perror("malloc(neighbour)");
99 return NULL;
100 }
101
102 neigh->hello.seqno = neigh->uhello.seqno = -1;
103 memcpy(neigh->address, address, 16);
104 neigh->txcost = INFINITY;
105 neigh->ihu_time = now;
106 neigh->hello.time = neigh->uhello.time = zero;
107 neigh->hello_rtt_receive_time = zero;
108 neigh->rtt_time = zero;
109 neigh->ifp = ifp;
110 neigh->buf.buf = buf;
111 neigh->buf.size = ifp->buf.size;
112 neigh->buf.hello = -1;
113 neigh->buf.flush_interval = ifp->buf.flush_interval;
114 neigh->buf.sin6.sin6_family = AF_INET6;
115 memcpy(&neigh->buf.sin6.sin6_addr, address, 16);
116 neigh->buf.sin6.sin6_port = htons(protocol_port);
117 neigh->buf.sin6.sin6_scope_id = ifp->ifindex;
118 neigh->next = neighs;
119 neighs = neigh;
120 local_notify_neighbour(neigh, LOCAL_ADD);
121 return neigh;
122 }
123
124 /* Recompute a neighbour's rxcost. Return true if anything changed.
125 This does not call local_notify_neighbour, see update_neighbour_metric. */
126 int
update_neighbour(struct neighbour * neigh,struct hello_history * hist,int unicast,int hello,int hello_interval)127 update_neighbour(struct neighbour *neigh, struct hello_history *hist,
128 int unicast, int hello, int hello_interval)
129 {
130 int missed_hellos;
131 int rc = 0;
132
133 if(hello < 0) {
134 if(hist->interval > 0)
135 missed_hellos =
136 ((int)timeval_minus_msec(&now, &hist->time) -
137 hist->interval * 7) /
138 (hist->interval * 10);
139 else
140 missed_hellos = 16; /* infinity */
141 if(missed_hellos <= 0)
142 return rc;
143 timeval_add_msec(&hist->time, &hist->time,
144 missed_hellos * hist->interval * 10);
145 } else {
146 if(hist->seqno >= 0 && hist->reach > 0) {
147 missed_hellos = seqno_minus(hello, hist->seqno) - 1;
148 if(missed_hellos < -8) {
149 /* Probably a neighbour that rebooted and lost its seqno.
150 Reboot the universe. */
151 hist->reach = 0;
152 missed_hellos = 0;
153 rc = 1;
154 } else if(missed_hellos < 0) {
155 /* Late hello. Probably due to the link layer buffering
156 packets during a link outage or a cpu overload. */
157 fprintf(stderr,
158 "Late hello: bufferbloated neighbor %s\n",
159 format_address(neigh->address));
160 hist->reach <<= -missed_hellos;
161 missed_hellos = 0;
162 rc = 1;
163 }
164 } else {
165 missed_hellos = 0;
166 }
167 if(hello_interval != 0) {
168 hist->time = now;
169 hist->interval = hello_interval;
170 }
171 }
172
173 if(missed_hellos > 0) {
174 if((unsigned)missed_hellos >= sizeof(hist->reach) * 8)
175 hist->reach = 0;
176 else
177 hist->reach >>= missed_hellos;
178 hist->seqno = seqno_plus(hist->seqno, missed_hellos);
179 rc = 1;
180 }
181
182 if(hello >= 0) {
183 hist->seqno = hello;
184 hist->reach >>= 1;
185 hist->reach |= 0x8000;
186 if((hist->reach & 0xFC00) != 0xFC00)
187 rc = 1;
188 }
189
190 return rc;
191 }
192
193 static int
reset_txcost(struct neighbour * neigh)194 reset_txcost(struct neighbour *neigh)
195 {
196 unsigned delay;
197
198 delay = timeval_minus_msec(&now, &neigh->ihu_time);
199
200 if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10 * 3)
201 return 0;
202
203 /* If we're losing a lot of packets, we probably lost an IHU too */
204 if(delay >= 180000 || (neigh->hello.reach & 0xFFF0) == 0 ||
205 (neigh->ihu_interval > 0 &&
206 delay >= neigh->ihu_interval * 10 * 10)) {
207 neigh->txcost = INFINITY;
208 neigh->ihu_time = now;
209 return 1;
210 }
211
212 return 0;
213 }
214
215 unsigned
neighbour_txcost(struct neighbour * neigh)216 neighbour_txcost(struct neighbour *neigh)
217 {
218 return neigh->txcost;
219 }
220
221 unsigned
check_neighbours()222 check_neighbours()
223 {
224 struct neighbour *neigh;
225 unsigned msecs = 50000;
226
227 debugf("Checking neighbours.\n");
228
229 neigh = neighs;
230 while(neigh) {
231 int changed, rc;
232 changed = update_neighbour(neigh, &neigh->hello, 0, -1, 0);
233 rc = update_neighbour(neigh, &neigh->uhello, 1, -1, 0);
234 changed = changed || rc;
235
236 if(neigh->hello.reach == 0 ||
237 neigh->hello.time.tv_sec > now.tv_sec || /* clock stepped */
238 timeval_minus_msec(&now, &neigh->hello.time) > 300000) {
239 struct neighbour *old = neigh;
240 neigh = neigh->next;
241 flush_neighbour(old);
242 continue;
243 }
244
245 rc = reset_txcost(neigh);
246 changed = changed || rc;
247
248 update_neighbour_metric(neigh, changed);
249
250 if(neigh->hello.interval > 0)
251 msecs = MIN(msecs, neigh->hello.interval * 10);
252 if(neigh->uhello.interval > 0)
253 msecs = MIN(msecs, neigh->uhello.interval * 10);
254 if(neigh->ihu_interval > 0)
255 msecs = MIN(msecs, neigh->ihu_interval * 10);
256 neigh = neigh->next;
257 }
258
259 return msecs;
260 }
261
262 /* To lose one hello is a misfortune, to lose two is carelessness. */
263 static int
two_three(int reach)264 two_three(int reach)
265 {
266 if((reach & 0xC000) == 0xC000)
267 return 1;
268 else if((reach & 0xC000) == 0)
269 return 0;
270 else if((reach & 0x2000))
271 return 1;
272 else
273 return 0;
274 }
275
276 unsigned
neighbour_rxcost(struct neighbour * neigh)277 neighbour_rxcost(struct neighbour *neigh)
278 {
279 unsigned delay, udelay;
280 unsigned short reach = neigh->hello.reach;
281 unsigned short ureach = neigh->uhello.reach;
282
283 delay = timeval_minus_msec(&now, &neigh->hello.time);
284 udelay = timeval_minus_msec(&now, &neigh->uhello.time);
285
286 if(((reach & 0xFFF0) == 0 || delay >= 180000) &&
287 ((ureach & 0xFFF0) == 0 || udelay >= 180000)) {
288 return INFINITY;
289 } else if((neigh->ifp->flags & IF_LQ)) {
290 int sreach =
291 ((reach & 0x8000) >> 2) +
292 ((reach & 0x4000) >> 1) +
293 (reach & 0x3FFF);
294 /* 0 <= sreach <= 0x7FFF */
295 int cost = (0x8000 * neigh->ifp->cost) / (sreach + 1);
296 /* cost >= interface->cost */
297 if(delay >= 40000)
298 cost = (cost * (delay - 20000) + 10000) / 20000;
299 return MIN(cost, INFINITY);
300 } else {
301 if(two_three(reach) || two_three(ureach))
302 return neigh->ifp->cost;
303 else
304 return INFINITY;
305 }
306 }
307
308 unsigned
neighbour_rttcost(struct neighbour * neigh)309 neighbour_rttcost(struct neighbour *neigh)
310 {
311 struct interface *ifp = neigh->ifp;
312
313 if(!ifp->max_rtt_penalty || !valid_rtt(neigh))
314 return 0;
315
316 /* Function: linear behaviour between rtt_min and rtt_max. */
317 if(neigh->rtt <= ifp->rtt_min) {
318 return 0;
319 } else if(neigh->rtt <= ifp->rtt_max) {
320 unsigned long long tmp =
321 (unsigned long long)ifp->max_rtt_penalty *
322 (neigh->rtt - ifp->rtt_min) /
323 (ifp->rtt_max - ifp->rtt_min);
324 assert((tmp & 0x7FFFFFFF) == tmp);
325 return tmp;
326 } else {
327 return ifp->max_rtt_penalty;
328 }
329 }
330
331 unsigned
neighbour_cost(struct neighbour * neigh)332 neighbour_cost(struct neighbour *neigh)
333 {
334 unsigned a, b, cost;
335
336 if(!if_up(neigh->ifp))
337 return INFINITY;
338
339 a = neighbour_txcost(neigh);
340
341 if(a >= INFINITY)
342 return INFINITY;
343
344 b = neighbour_rxcost(neigh);
345 if(b >= INFINITY)
346 return INFINITY;
347
348 if(!(neigh->ifp->flags & IF_LQ) || (a < 256 && b < 256)) {
349 cost = a;
350 } else {
351 /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
352 probabilities of a packet getting through in the direct and reverse
353 directions. */
354 a = MAX(a, 256);
355 b = MAX(b, 256);
356 /* 1/(alpha * beta), which is just plain ETX. */
357 /* Since a and b are capped to 16 bits, overflow is impossible. */
358 cost = (a * b + 128) >> 8;
359 }
360
361 cost += neighbour_rttcost(neigh);
362
363 return MIN(cost, INFINITY);
364 }
365
366 int
valid_rtt(struct neighbour * neigh)367 valid_rtt(struct neighbour *neigh)
368 {
369 return (timeval_minus_msec(&now, &neigh->rtt_time) < 180000) ? 1 : 0;
370 }
371