1 /* VDE_ROUTER (C) 2007:2012 Daniele Lacamera
3 * Time-conversion functions by Julien Duraj <julien@duraj.fr>
4 * Licensed under the GPLv2
5 * OLSR implementation loosely based on RFC3626 :)
10 #include "vder_olsr.h"
17 #define OLSR_MSG_INTERVAL 2000
18 #define DGRAM_MAX_SIZE 1800
19 #define HOST_NETMASK (htonl(0xFFFFFFFF))
21 # define MIN(a,b) (a<b?a:b)
24 #define fresher(a,b) ((a>b) || ((b - a) > 32768))
26 static struct vder_udp_socket
*udpsock
;
27 static struct olsr_setup
*settings
;
29 uint16_t fresh_ansn
= 0;
31 struct olsr_route_entry
33 struct olsr_route_entry
*next
;
36 struct olsr_route_entry
*gateway
;
37 struct vder_iface
*iface
;
40 struct olsr_route_entry
*children
;
43 uint8_t *advertised_tc
;
46 static struct olsr_route_entry
*Local_interfaces
;
48 struct olsr_route_entry
*olsr_get_ethentry(struct vder_iface
*vif
)
50 struct olsr_route_entry
*cur
= Local_interfaces
;
52 if (cur
->iface
== vif
)
59 static struct olsr_route_entry
*get_next_hop(struct olsr_route_entry
*dst
)
61 struct olsr_route_entry
*hop
= dst
;
70 static inline void olsr_route_add(struct olsr_route_entry
*el
)
72 struct olsr_route_entry
*nexthop
;
74 if (fresher(fresh_ansn
, my_ansn
))
75 my_ansn
= fresh_ansn
+ 1;
80 /* 2-hops route or more */
81 el
->next
= el
->gateway
->children
;
82 el
->gateway
->children
= el
;
83 nexthop
= get_next_hop(el
);
84 vder_route_add(el
->destination
, HOST_NETMASK
, nexthop
->destination
, el
->metric
, NULL
);
85 el
->link_type
= OLSRLINK_MPR
;
86 } else if (el
->iface
) {
88 struct olsr_route_entry
*ei
= olsr_get_ethentry(el
->iface
);
89 el
->link_type
= OLSRLINK_SYMMETRIC
;
91 el
->next
= ei
->children
;
97 static inline void olsr_route_del(struct olsr_route_entry
*r
)
99 struct olsr_route_entry
*cur
, *prev
= NULL
, *lst
;
100 if (fresher(fresh_ansn
, my_ansn
))
101 my_ansn
= fresh_ansn
+ 1;
103 lst
= r
->gateway
->children
;
104 } else if (r
->iface
) {
105 lst
= olsr_get_ethentry(r
->iface
);
107 lst
= Local_interfaces
;
109 cur
= lst
, prev
= NULL
;
114 vder_route_del(r
->destination
, HOST_NETMASK
, r
->metric
);
117 r
->gateway
->children
= r
->next
;
119 prev
->next
= r
->next
;
122 while (r
->children
) {
123 olsr_route_del(r
->children
);
124 /* Orphans must die. */
134 static struct olsr_route_entry
*get_route_by_address(struct olsr_route_entry
*lst
, uint32_t ip
)
136 struct olsr_route_entry
*found
;
138 if (lst
->destination
== ip
) {
141 found
= get_route_by_address(lst
->children
, ip
);
144 found
= get_route_by_address(lst
->next
, ip
);
151 #define OSLR_C 1/16.0
152 #define DEFAULT_VTIME 288UL
154 uint8_t seconds2olsr(uint32_t seconds
)
158 /* find largest b such as seconds/C >= 2^b */
159 for (b
= 0; b
<= 0x0f; b
++) {
160 if (seconds
* 16 < (1 << b
)){
165 /* compute the expression 16*(T/(C*(2^b))-1), which may not be a
166 integer, and round it up. This results in the value for 'a' */
167 a
= 16 * (seconds
/ (OSLR_C
* (1 << b
)) - 1);
169 /* if 'a' is equal to 16: increment 'b' by one, and set 'a' to 0 */
177 uint32_t olsr2seconds(uint8_t olsr
)
182 return OSLR_C
* (1 + a
/16.0) * (1 << b
);
186 static void refresh_neighbors(struct vder_iface
*iface
)
188 uint32_t neighbors
[256];
190 struct olsr_route_entry
*found
= NULL
, *ancestor
= NULL
;
191 int n_vec_size
= vder_arp_get_neighbors(iface
, neighbors
, 256);
193 ancestor
= olsr_get_ethentry(iface
);
197 for (i
= 0; i
< n_vec_size
; i
++) {
198 found
= get_route_by_address(Local_interfaces
, neighbors
[i
]);
200 if (found
->metric
> 1) { /* Reposition among neighbors */
201 olsr_route_del(found
);
202 found
->gateway
= olsr_get_ethentry(iface
);
203 found
->iface
= iface
;
207 olsr_route_add(found
);
209 found
->link_type
= OLSRLINK_SYMMETRIC
;
210 found
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
212 struct olsr_route_entry
*e
= malloc(sizeof (struct olsr_route_entry
));
214 perror("olsr: adding local route entry");
217 memset(e
, 0, sizeof(struct olsr_route_entry
));
218 e
->destination
= neighbors
[i
];
219 e
->link_type
= OLSRLINK_SYMMETRIC
;
220 e
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
221 e
->gateway
= olsr_get_ethentry(iface
);
231 static void olsr_garbage_collector(struct olsr_route_entry
*sublist
)
235 if ((sublist
->time_left
--) <= 0) {
236 olsr_route_del(sublist
);
240 olsr_garbage_collector(sublist
->children
);
241 olsr_garbage_collector(sublist
->next
);
245 static void refresh_routes(void)
248 struct olsr_route_entry
*local
, *neighbor
= NULL
;
250 /* Refresh local entries */
252 /* Step 1: set zero expire time for local addresses and neighbors*/
253 local
= Local_interfaces
;
255 local
->time_left
= 0;
256 neighbor
= local
->children
;
257 while (neighbor
&& (neighbor
->metric
< 2)) {
258 //printf("Setting to zero. Neigh: %08x metric %d\n", neighbor->destination, neighbor->metric);
259 neighbor
->time_left
= 0;
260 neighbor
= neighbor
->next
;
265 /* Step 2: refresh timer for entries that are still valid.
268 for (i
= 0; i
< settings
->n_ifaces
; i
++) {
269 struct vder_iface
*icur
= settings
->ifaces
[i
];
270 local
= olsr_get_ethentry(icur
);
272 local
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
273 } else if (icur
->address_list
) {
274 struct olsr_route_entry
*e
= malloc(sizeof (struct olsr_route_entry
));
276 perror("olsr: adding local route entry");
279 memset(e
, 0, sizeof(struct olsr_route_entry
));
280 e
->destination
= icur
->address_list
->address
; /* Always pick the first address */
281 e
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
286 e
->next
= Local_interfaces
;
287 Local_interfaces
= e
;
289 refresh_neighbors(icur
);
294 static int olsr_build_hello_neighbors(uint8_t *buf
, int size
)
297 struct olsr_route_entry
*local
, *neighbor
;
298 struct olsr_neighbor
*dst
= (struct olsr_neighbor
*) buf
;
299 local
= Local_interfaces
;
301 neighbor
= local
->children
;
303 struct olsr_link
*li
= (struct olsr_link
*) (buf
+ ret
);
304 li
->link_code
= neighbor
->link_type
;
306 li
->link_msg_size
= htons(sizeof(struct olsr_neighbor
) + sizeof(struct olsr_link
));
307 ret
+= sizeof(struct olsr_link
);
308 dst
= (struct olsr_neighbor
*) (buf
+ret
);
309 dst
->addr
= neighbor
->destination
;
310 dst
->nlq
= neighbor
->nlq
;
311 dst
->lq
= neighbor
->lq
;
313 ret
+= sizeof(struct olsr_neighbor
);
315 return ret
- sizeof(struct olsr_neighbor
) - sizeof(struct olsr_link
);
316 neighbor
= neighbor
->next
;
323 static int olsr_build_tc_neighbors(uint8_t *buf
, int size
)
326 struct olsr_route_entry
*local
, *neighbor
;
327 struct olsr_neighbor
*dst
= (struct olsr_neighbor
*) buf
;
328 local
= Local_interfaces
;
330 neighbor
= local
->children
;
332 dst
->addr
= neighbor
->destination
;
333 dst
->nlq
= neighbor
->nlq
;
334 dst
->lq
= neighbor
->lq
;
336 ret
+= sizeof(struct olsr_neighbor
);
337 dst
= (struct olsr_neighbor
*) (buf
+ ret
);
339 return ret
- sizeof(struct olsr_neighbor
);
340 neighbor
= neighbor
->next
;
347 static int olsr_build_mid(uint8_t *buf
, int size
, struct vder_iface
*excluded
)
350 struct olsr_route_entry
*local
;
351 uint32_t *dst
= (uint32_t *) buf
;
352 local
= Local_interfaces
;
354 if (local
->iface
!= excluded
) {
355 *dst
= local
->destination
;
356 ret
+= sizeof(uint32_t);
357 dst
= (uint32_t *) (buf
+ ret
);
359 return ret
- sizeof(uint32_t);
366 static uint16_t pkt_counter
= 0;
367 static void olsr_make_dgram(struct vder_iface
*vif
)
369 uint8_t dgram
[DGRAM_MAX_SIZE
];
371 struct vder_ip4address
*ep
;
372 struct olsrhdr
*ohdr
;
373 uint32_t netmask
, bcast
;
374 struct olsrmsg
*msg_hello
, *msg_mid
, *msg_tc
;
375 struct olsr_hmsg_hello
*hello
;
376 struct olsr_hmsg_tc
*tc
;
377 static uint8_t hello_counter
= 0, mid_counter
= 0, tc_counter
= 0;
379 ohdr
= (struct olsrhdr
*)dgram
;
380 size
+= sizeof(struct olsrhdr
);
382 ep
= vif
->address_list
; /* Take first address */
385 netmask
= vder_get_netmask(vif
, ep
->address
);
386 bcast
= vder_get_broadcast(ep
->address
, netmask
);
392 msg_hello
= (struct olsrmsg
*) (dgram
+ size
);
393 size
+= sizeof(struct olsrmsg
);
394 msg_hello
->type
= OLSRMSG_HELLO
;
395 msg_hello
->vtime
= seconds2olsr(DEFAULT_VTIME
);
396 msg_hello
->orig
= ep
->address
;
399 msg_hello
->seq
= htons(hello_counter
++);
400 hello
= (struct olsr_hmsg_hello
*)(dgram
+ size
);
401 size
+= sizeof(struct olsr_hmsg_hello
);
403 hello
->htime
= 0x05; /* Todo: find and define values */
404 hello
->willingness
= 0x07;
405 r
= olsr_build_hello_neighbors(dgram
+ size
, DGRAM_MAX_SIZE
- size
);
407 perror("Building hello message");
411 msg_hello
->size
= htons(sizeof(struct olsrmsg
) + sizeof(struct olsr_hmsg_hello
) + r
);
415 msg_mid
= (struct olsrmsg
*)(dgram
+ size
);
416 size
+= sizeof(struct olsrmsg
);
417 msg_mid
->type
= OLSRMSG_MID
;
418 msg_mid
->vtime
= seconds2olsr(60);
419 msg_mid
->orig
= ep
->address
;
422 msg_mid
->seq
= htons(mid_counter
++);
423 r
= olsr_build_mid(dgram
+ size
, DGRAM_MAX_SIZE
- size
, vif
);
425 perror("Building mid message");
429 size
-= sizeof(struct olsrmsg
);
432 msg_mid
->size
= htons(sizeof(struct olsrmsg
) + r
);
435 msg_tc
= (struct olsrmsg
*) (dgram
+ size
);
436 size
+= sizeof(struct olsrmsg
);
437 msg_tc
->type
= OLSRMSG_TC
;
438 msg_tc
->vtime
= seconds2olsr(DEFAULT_VTIME
);
439 msg_tc
->orig
= ep
->address
;
442 msg_tc
->seq
= htons(tc_counter
++);
443 tc
= (struct olsr_hmsg_tc
*)(dgram
+ size
);
444 size
+= sizeof(struct olsr_hmsg_tc
);
445 tc
->ansn
= htons(my_ansn
);
446 r
= olsr_build_tc_neighbors(dgram
+ size
, DGRAM_MAX_SIZE
- size
);
448 perror("Building tc message");
452 msg_tc
->size
= htons(sizeof(struct olsrmsg
) + sizeof(struct olsr_hmsg_tc
) + r
);
454 /* Finalize olsr packet */
455 ohdr
->len
= htons(size
);
456 ohdr
->seq
= htons(pkt_counter
++);
458 /* Send the thing out */
459 if ( 0 > vder_udpsocket_sendto_broadcast(udpsock
, dgram
, size
, vif
, bcast
, OLSR_PORT
) ) {
464 static inline void arp_storm(uint32_t addr
)
467 for (i
= 0; i
< settings
->n_ifaces
; i
++) {
468 vder_arp_query(settings
->ifaces
[i
], addr
);
472 static void recv_mid(uint8_t *buffer
, int len
, struct olsr_route_entry
*origin
)
476 struct olsr_route_entry
*e
;
478 if (len
% sizeof(uint32_t)) /*drop*/
481 while (len
> parsed
) {
482 address
= (uint32_t *)(buffer
+ parsed
);
483 e
= get_route_by_address(Local_interfaces
, *address
);
485 e
= malloc(sizeof(struct olsr_route_entry
));
487 perror("olsr allocating route");
490 memset(e
, 0, sizeof(struct olsr_route_entry
));
491 e
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
492 e
->destination
= *address
;
494 e
->iface
= origin
->iface
;
495 e
->metric
= origin
->metric
+ 1;
497 e
->nlq
= origin
->nlq
;
499 arp_storm(e
->destination
);
500 } else if (e
->metric
> (origin
->metric
+ 1)) {
502 e
->metric
= origin
->metric
;
506 parsed
+= sizeof(uint32_t);
510 static void recv_hello(uint8_t *buffer
, int len
, struct olsr_route_entry
*origin
)
512 struct olsr_link
*li
;
513 struct olsr_route_entry
*e
;
515 struct olsr_neighbor
*neigh
;
520 while (len
> parsed
) {
521 li
= (struct olsr_link
*) buffer
;
522 neigh
= (struct olsr_neighbor
*)(buffer
+ parsed
+ sizeof(struct olsr_link
));
523 parsed
+= ntohs(li
->link_msg_size
);
524 e
= get_route_by_address(Local_interfaces
, neigh
->addr
);
526 e
= malloc(sizeof(struct olsr_route_entry
));
528 perror("olsr allocating route");
531 memset(e
, 0, sizeof(struct olsr_route_entry
));
532 e
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
533 e
->destination
= neigh
->addr
;
535 e
->iface
= origin
->iface
;
536 e
->metric
= origin
->metric
+ 1;
537 e
->link_type
= OLSRLINK_UNKNOWN
;
538 e
->lq
= MIN(origin
->lq
, neigh
->lq
);
539 e
->nlq
= MIN(origin
->nlq
, neigh
->nlq
);
541 arp_storm(e
->destination
);
542 } else if ((e
->gateway
!= origin
) && (e
->metric
> (origin
->metric
+ 1))) {
544 e
->metric
= origin
->metric
+ 1;
551 static int reconsider_topology(uint8_t *buf
, int size
, struct olsr_route_entry
*e
)
553 struct olsr_hmsg_tc
*tc
= (struct olsr_hmsg_tc
*) buf
;
554 uint16_t new_ansn
= ntohs(tc
->ansn
);
555 int parsed
= sizeof(struct olsr_hmsg_tc
);
556 struct olsr_route_entry
*rt
;
557 struct olsr_neighbor
*n
;
559 if (e
->advertised_tc
&& fresher(new_ansn
, e
->ansn
))
561 free(e
->advertised_tc
);
562 e
->advertised_tc
= NULL
;
565 if (fresher(new_ansn
, fresh_ansn
)) {
566 fresh_ansn
= new_ansn
;
569 if (!e
->advertised_tc
) {
570 e
->advertised_tc
= malloc(size
);
572 perror("Allocating forward packet");
575 memcpy(e
->advertised_tc
, buf
, size
);
577 while (parsed
< size
) {
578 n
= (struct olsr_neighbor
*) (buf
+ parsed
);
579 parsed
+= sizeof(struct olsr_neighbor
);
580 rt
= get_route_by_address(Local_interfaces
, n
->addr
);
581 if (rt
&& (rt
->gateway
== e
)) {
582 /* Refresh existing node */
583 rt
->time_left
= e
->time_left
;
584 } else if (!rt
|| (rt
->metric
> (e
->metric
+ 1)) || (rt
->nlq
< n
->nlq
)) {
586 rt
= malloc(sizeof (struct olsr_route_entry
));
587 memset(rt
, 0, sizeof(struct olsr_route_entry
));
588 rt
->destination
= n
->addr
;
592 rt
->link_type
= OLSRLINK_UNKNOWN
;
593 rt
->iface
= e
->iface
;
595 rt
->metric
= e
->metric
+ 1;
598 rt
->time_left
= e
->time_left
;
608 static void olsr_recv(uint8_t *buffer
, int len
)
611 struct olsrhdr
*outohdr
, *oh
= (struct olsrhdr
*) buffer
;
612 struct olsr_route_entry
*ancestor
;
614 uint8_t outmsg
[DGRAM_MAX_SIZE
];
616 if (len
!= ntohs(oh
->len
)) {
619 parsed
+= sizeof(struct olsrhdr
);
621 outohdr
= (struct olsrhdr
*)outmsg
;
622 outsize
+= sizeof(struct olsrhdr
);
624 while (len
> parsed
) {
625 struct olsr_route_entry
*origin
;
626 msg
= (struct olsrmsg
*) (buffer
+ parsed
);
627 origin
= get_route_by_address(Local_interfaces
, msg
->orig
);
629 /* Discard this msg while it is not from known host */
630 arp_storm(msg
->orig
);
631 parsed
+= ntohs(msg
->size
);
634 /* We know this is a Master host and a neighbor */
635 origin
->link_type
= OLSRLINK_MPR
;
636 origin
->time_left
= olsr2seconds(msg
->vtime
);
639 ancestor
= olsr_get_ethentry(origin
->iface
);
640 if ((origin
->metric
> 1) && ancestor
) {
641 olsr_route_del(origin
);
642 origin
->gateway
= ancestor
;
644 olsr_route_add(origin
);
646 recv_hello(buffer
+ parsed
+ sizeof(struct olsrmsg
) + sizeof(struct olsr_hmsg_hello
),
647 ntohs(msg
->size
) - (sizeof(struct olsrmsg
)) - sizeof(struct olsr_hmsg_hello
),
652 recv_mid(buffer
+ parsed
+ sizeof(struct olsrmsg
), ntohs(msg
->size
) - (sizeof(struct olsrmsg
)), origin
);
655 if (reconsider_topology(buffer
+ parsed
+ sizeof(struct olsrmsg
), ntohs(msg
->size
) - (sizeof(struct olsrmsg
)), origin
) < 1)
658 msg
->hop
= origin
->metric
;
664 if ((--msg
->ttl
) > 0) {
665 memcpy(outmsg
+ outsize
, msg
, ntohs(msg
->size
));
666 outsize
+= ntohs(msg
->size
);
668 parsed
+= ntohs(msg
->size
);
671 if (outsize
> sizeof(struct olsrhdr
)) {
673 uint32_t netmask
, bcast
;
674 struct vder_ip4address
*addr
;
675 struct vder_iface
*vif
;
676 /* Finalize FWD packet */
677 outohdr
->len
= htons(outsize
);
678 outohdr
->seq
= htons(pkt_counter
++);
681 /* Send the thing out */
682 for (j
= 0; j
< settings
->n_ifaces
; j
++) {
683 vif
= settings
->ifaces
[j
];
684 addr
= vif
->address_list
; /* Take first address */
687 netmask
= vder_get_netmask(vif
, addr
->address
);
688 bcast
= vder_get_broadcast(addr
->address
, netmask
);
689 if ( 0 > vder_udpsocket_sendto_broadcast(udpsock
, outmsg
, outsize
, vif
, bcast
, OLSR_PORT
) ) {
697 void *vder_olsr_loop(void *olsr_settings
)
701 unsigned char buffer
[DGRAM_MAX_SIZE
];
704 struct timeval now
, last_out
;
706 settings
= (struct olsr_setup
*) olsr_settings
;
707 if(settings
->n_ifaces
<= 0)
710 udpsock
= vder_udpsocket_open(OLSR_PORT
);
714 for (i
= 0; i
< settings
->n_ifaces
; i
++) {
715 struct vder_ip4address
*a
= settings
->ifaces
[i
]->address_list
;
717 struct olsr_route_entry
*e
= malloc(sizeof(struct olsr_route_entry
));
719 perror("initializing interfaces");
722 memset(e
, 0, sizeof(struct olsr_route_entry
));
723 e
->destination
= a
->address
;
724 e
->link_type
= OLSRLINK_SYMMETRIC
;
725 e
->time_left
= (OLSR_MSG_INTERVAL
<< 2);
727 e
->iface
= settings
->ifaces
[i
];
731 e
->next
= Local_interfaces
;
732 Local_interfaces
= e
;
737 gettimeofday(&last_out
, NULL
);
741 len
= vder_udpsocket_recvfrom(udpsock
, buffer
, DGRAM_MAX_SIZE
, &from_ip
, &from_port
, 100);
746 if ((len
> 0) && (from_port
== OLSR_PORT
)) {
747 olsr_recv(buffer
, len
);
750 gettimeofday(&now
, NULL
);
751 if (last_out
.tv_sec
== now
.tv_sec
)
753 /* Remove expired entries */
754 olsr_garbage_collector(Local_interfaces
);
757 for (i
= 0; i
< settings
->n_ifaces
; i
++)
758 olsr_make_dgram(settings
->ifaces
[i
]);