2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2003, Andreas Tønnesen (andreto@olsr.org)
4 * 2004, Thomas Lopatic (thomas@lopatic.de)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
34 * Visit http://www.olsr.org for more information.
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
40 * $Id: lq_packet.c,v 1.8 2004/12/04 17:06:57 tlopatic Exp $
43 #include "olsr_protocol.h"
45 #include "interfaces.h"
47 #include "neighbor_table.h"
48 #include "mpr_selector_set.h"
51 #include "process_package.h" // XXX - remove
52 #include "two_hop_neighbor_table.h"
53 #include "hysteresis.h"
55 static unsigned char msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE];
58 create_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
60 struct lq_hello_neighbor *neigh;
61 struct link_entry *walker;
63 // initialize the static fields
65 lq_hello->comm.type = LQ_HELLO_MESSAGE;
66 lq_hello->comm.vtime = me_to_double(outif->valtimes.hello);
67 lq_hello->comm.size = 0;
69 COPY_IP(&lq_hello->comm.orig, &main_addr);
71 lq_hello->comm.ttl = 1;
72 lq_hello->comm.hops = 0;
73 lq_hello->comm.seqno = get_msg_seqno();
75 lq_hello->htime = me_to_double(outif->hello_etime);
76 lq_hello->will = olsr_cnf->willingness;
78 lq_hello->neigh = NULL;
80 // loop through the link set
82 for (walker = link_set; walker != NULL; walker = walker->next)
84 // allocate a neighbour entry
86 neigh = olsr_malloc(sizeof (struct lq_hello_neighbor), "Build LQ_HELLO");
88 // a) this neighbor interface IS NOT visible via the output interface
90 if(!COMP_IP(&walker->local_iface_addr, &outif->ip_addr))
91 neigh->link_type = UNSPEC_LINK;
93 // b) this neighbor interface IS visible via the output interface
96 neigh->link_type = lookup_link_status(walker);
98 // set the entry's link quality
100 neigh->link_quality = walker->loss_link_quality;
101 neigh->neigh_link_quality = walker->neigh_link_quality;
103 // set the entry's neighbour type
105 if(walker->neighbor->is_mpr)
106 neigh->neigh_type = MPR_NEIGH;
108 else if (walker->neighbor->status == SYM)
109 neigh->neigh_type = SYM_NEIGH;
111 else if (walker->neighbor->status == NOT_SYM)
112 neigh->neigh_type = NOT_NEIGH;
114 // set the entry's neighbour interface address
116 COPY_IP(&neigh->addr, &walker->neighbor_iface_addr);
118 // queue the neighbour entry
120 neigh->next = lq_hello->neigh;
121 lq_hello->neigh = neigh;
126 destroy_lq_hello(struct lq_hello_message *lq_hello)
128 struct lq_hello_neighbor *walker, *aux;
130 // loop through the queued neighbour entries and free them
132 for (walker = lq_hello->neigh; walker != NULL; walker = aux)
138 lq_hello->neigh = NULL;
142 create_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
144 struct lq_tc_neighbor *neigh;
146 struct neighbor_entry *walker;
147 struct link_entry *link;
149 // initialize the static fields
151 lq_tc->comm.type = LQ_TC_MESSAGE;
152 lq_tc->comm.vtime = me_to_double(outif->valtimes.tc);
153 lq_tc->comm.size = 0;
155 COPY_IP(&lq_tc->comm.orig, &main_addr);
157 lq_tc->comm.ttl = MAX_TTL;
158 lq_tc->comm.hops = 0;
159 lq_tc->comm.seqno = get_msg_seqno();
161 COPY_IP(&lq_tc->from, &main_addr);
167 // loop through all neighbours
169 for(i = 0; i < HASHSIZE; i++)
171 for(walker = neighbortable[i].next; walker != &neighbortable[i];
172 walker = walker->next)
174 // only consider symmetric neighbours
176 if(walker->status != SYM)
179 // TC redundancy == 1: only consider MPRs and MPR selectors
181 if (olsr_cnf->tc_redundancy == 1 && !walker->is_mpr &&
182 olsr_lookup_mprs_set(&walker->neighbor_main_addr) == NULL)
185 // TC redundancy == 0: only consider MPR selectors
187 else if (olsr_cnf->tc_redundancy == 0 &&
188 olsr_lookup_mprs_set(&walker->neighbor_main_addr) == NULL)
191 // allocate a neighbour entry
193 neigh = olsr_malloc(sizeof (struct lq_tc_neighbor), "Build LQ_TC");
195 // set the entry's main address
197 COPY_IP(&neigh->main, &walker->neighbor_main_addr);
199 // set the entry's link quality
201 link = olsr_neighbor_best_link(&neigh->main);
203 neigh->link_quality = link->loss_link_quality;
204 neigh->neigh_link_quality = link->neigh_link_quality;
206 // queue the neighbour entry
208 neigh->next = lq_tc->neigh;
209 lq_tc->neigh = neigh;
215 destroy_lq_tc(struct lq_tc_message *lq_tc)
217 struct lq_tc_neighbor *walker, *aux;
219 // loop through the queued neighbour entries and free them
221 for (walker = lq_tc->neigh; walker != NULL; walker = aux)
228 static int common_size(void)
230 // return the size of the header shared by all OLSR messages
232 return (olsr_cnf->ip_version == AF_INET) ?
233 sizeof (struct olsr_header_v4) : sizeof (struct olsr_header_v6);
236 static void serialize_common(struct olsr_common *comm)
238 struct olsr_header_v4 *olsr_head_v4;
239 struct olsr_header_v6 *olsr_head_v6;
241 // serialize an IPv4 OLSR message header
243 if (olsr_cnf->ip_version == AF_INET)
245 olsr_head_v4 = (struct olsr_header_v4 *)msg_buffer;
247 olsr_head_v4->type = comm->type;
248 olsr_head_v4->vtime = double_to_me(comm->vtime);
249 olsr_head_v4->size = htons(comm->size);
251 COPY_IP(&olsr_head_v4->orig, &comm->orig);
253 olsr_head_v4->ttl = comm->ttl;
254 olsr_head_v4->hops = comm->hops;
255 olsr_head_v4->seqno = htons(comm->seqno);
260 // serialize an IPv6 OLSR message header
262 olsr_head_v6 = (struct olsr_header_v6 *)msg_buffer;
264 olsr_head_v6->type = comm->type;
265 olsr_head_v6->vtime = double_to_me(comm->vtime);
266 olsr_head_v6->size = htons(comm->size);
268 COPY_IP(&olsr_head_v6->orig, &comm->orig);
270 olsr_head_v6->ttl = comm->ttl;
271 olsr_head_v6->hops = comm->hops;
272 olsr_head_v6->seqno = htons(comm->seqno);
276 serialize_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
278 int off, rem, size, req;
279 struct lq_hello_header *head;
280 struct lq_hello_info_header *info_head;
281 struct lq_hello_neighbor *neigh;
286 if (lq_hello == NULL || outif == NULL)
289 // leave space for the OLSR header
293 // initialize the LQ_HELLO header
295 head = (struct lq_hello_header *)(msg_buffer + off);
298 head->htime = double_to_me(lq_hello->htime);
299 head->will = lq_hello->will;
301 // 'off' is the offset of the byte following the LQ_HELLO header
303 off += sizeof (struct lq_hello_header);
305 // our work buffer starts at 'off'...
307 buff = msg_buffer + off;
309 // ... that's why we start with a 'size' of 0 and subtract 'off' from
310 // the remaining bytes in the output buffer
313 rem = net_outbuffer_bytes_left(outif) - off;
315 // initially, we want to put at least an info header, an IP address,
316 // and the corresponding link quality into the message
318 if (rem < sizeof (struct lq_hello_info_header) + ipsize + 4)
322 rem = net_outbuffer_bytes_left(outif) - off;
327 // iterate through all neighbor types ('i') and all link types ('j')
329 for (i = 0; i <= MAX_NEIGH; i++)
331 for(j = 0; j <= MAX_LINK; j++)
338 // loop through neighbors
340 for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next)
342 if (neigh->neigh_type != i || neigh->link_type != j)
345 // we need space for an IP address plus link quality
350 // no, we also need space for an info header, as this is the
351 // first neighbor with the current neighor type and link type
354 req += sizeof (struct lq_hello_info_header);
356 // we do not have enough space left
358 if (size + req > rem)
360 // finalize the OLSR header
362 lq_hello->comm.size = size + off;
364 serialize_common((struct olsr_common *)lq_hello);
366 // finalize the info header
369 ntohs(buff + size - (unsigned char *)info_head);
373 net_outbuffer_push(outif, msg_buffer, size + off);
377 // move to the beginning of the buffer
380 rem = net_outbuffer_bytes_left(outif) - off;
382 // we need a new info header
387 // create a new info header
391 info_head = (struct lq_hello_info_header *)(buff + size);
392 size += sizeof (struct lq_hello_info_header);
394 info_head->reserved = 0;
395 info_head->link_code = CREATE_LINK_CODE(i, j);
398 // add the current neighbor's IP address
400 COPY_IP(buff + size, &neigh->addr);
403 // add the corresponding link quality
405 buff[size++] = (unsigned char)(neigh->link_quality * 255);
406 buff[size++] = (unsigned char)(neigh->neigh_link_quality * 255);
416 // finalize the info header, if there are any neighbors with the
417 // current neighbor type and link type
420 info_head->size = ntohs(buff + size - (unsigned char *)info_head);
424 // finalize the OLSR header
426 lq_hello->comm.size = size + off;
428 serialize_common((struct olsr_common *)lq_hello);
430 // move the message to the output buffer
432 net_outbuffer_push(outif, msg_buffer, size + off);
436 serialize_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
439 struct lq_tc_header *head;
440 struct lq_tc_neighbor *neigh;
443 if (lq_tc == NULL || outif == NULL)
446 // leave space for the OLSR header
450 // initialize the LQ_TC header
452 head = (struct lq_tc_header *)(msg_buffer + off);
454 head->ansn = htons(lq_tc->ansn);
457 // 'off' is the offset of the byte following the LQ_TC header
459 off += sizeof (struct lq_tc_header);
461 // our work buffer starts at 'off'...
463 buff = msg_buffer + off;
465 // ... that's why we start with a 'size' of 0 and subtract 'off' from
466 // the remaining bytes in the output buffer
469 rem = net_outbuffer_bytes_left(outif) - off;
471 // initially, we want to put at least an IP address and the corresponding
472 // link quality into the message
474 if (rem < ipsize + 4)
478 rem = net_outbuffer_bytes_left(outif) - off;
481 // loop through neighbors
483 for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next)
485 // we need space for an IP address plus link quality
488 if (size + ipsize + 4 > rem)
490 // finalize the OLSR header
492 lq_tc->comm.size = size + off;
494 serialize_common((struct olsr_common *)lq_tc);
498 net_outbuffer_push(outif, msg_buffer, size + off);
502 // move to the beginning of the buffer
505 rem = net_outbuffer_bytes_left(outif) - off;
508 // add the current neighbor's IP address
510 COPY_IP(buff + size, &neigh->main);
513 // add the corresponding link quality
515 buff[size++] = (unsigned char)(neigh->link_quality * 255);
516 buff[size++] = (unsigned char)(neigh->neigh_link_quality * 255);
524 // finalize the OLSR header
526 lq_tc->comm.size = size + off;
528 serialize_common((struct olsr_common *)lq_tc);
530 net_outbuffer_push(outif, msg_buffer, size + off);
533 static void *deserialize_common(struct olsr_common *comm, void *ser)
535 struct olsr_header_v4 *olsr_head_v4;
536 struct olsr_header_v6 *olsr_head_v6;
538 // deserialize an IPv4 OLSR message header
540 if (olsr_cnf->ip_version == AF_INET)
542 olsr_head_v4 = (struct olsr_header_v4 *)ser;
544 comm->type = olsr_head_v4->type;
545 comm->vtime = me_to_double(olsr_head_v4->vtime);
546 comm->size = ntohs(olsr_head_v4->size);
548 COPY_IP(&comm->orig, &olsr_head_v4->orig);
550 comm->ttl = olsr_head_v4->ttl;
551 comm->hops = olsr_head_v4->hops;
552 comm->seqno = ntohs(olsr_head_v4->seqno);
554 return (void *)(olsr_head_v4 + 1);
557 // deserialize an IPv6 OLSR message header
559 olsr_head_v6 = (struct olsr_header_v6 *)ser;
561 comm->type = olsr_head_v6->type;
562 comm->vtime = me_to_double(olsr_head_v6->vtime);
563 comm->size = ntohs(olsr_head_v6->size);
565 COPY_IP(&comm->orig, &olsr_head_v6->orig);
567 comm->ttl = olsr_head_v6->ttl;
568 comm->hops = olsr_head_v6->hops;
569 comm->seqno = ntohs(olsr_head_v6->seqno);
571 return (void *)(olsr_head_v6 + 1);
575 deserialize_lq_hello(struct lq_hello_message *lq_hello, void *ser)
577 struct lq_hello_header *head;
578 struct lq_hello_info_header *info_head;
579 unsigned char *curr, *limit, *limit2;
580 struct lq_hello_neighbor *neigh;
582 lq_hello->neigh = NULL;
587 head = (struct lq_hello_header *)
588 deserialize_common((struct olsr_common *)lq_hello, ser);
590 if (lq_hello->comm.type != LQ_HELLO_MESSAGE)
593 limit = ((unsigned char *)ser) + lq_hello->comm.size;
595 lq_hello->htime = me_to_double(head->htime);
596 lq_hello->will = head->will;
598 lq_hello->neigh = NULL;
600 curr = (unsigned char *)(head + 1);
604 info_head = (struct lq_hello_info_header *)curr;
606 limit2 = curr + ntohs(info_head->size);
608 curr = (unsigned char *)(info_head + 1);
610 while (curr < limit2)
612 neigh = olsr_malloc(sizeof (struct lq_hello_neighbor),
613 "LQ_HELLO deserialization");
615 COPY_IP(&neigh->addr, curr);
618 neigh->link_quality = (double)*curr++ / 255.0;
619 neigh->neigh_link_quality = (double)*curr++ / 255.0;
623 neigh->link_type = EXTRACT_LINK(info_head->link_code);
624 neigh->neigh_type = EXTRACT_STATUS(info_head->link_code);
626 neigh->next = lq_hello->neigh;
627 lq_hello->neigh = neigh;
633 deserialize_lq_tc(struct lq_tc_message *lq_tc, void *ser,
634 union olsr_ip_addr *from)
636 struct lq_tc_header *head;
637 union olsr_ip_addr *addr;
638 unsigned char *curr, *limit;
639 struct lq_tc_neighbor *neigh;
646 head = (struct lq_tc_header *)
647 deserialize_common((struct olsr_common *)lq_tc, ser);
649 if (lq_tc->comm.type != LQ_TC_MESSAGE)
652 limit = ((unsigned char *)ser) + lq_tc->comm.size;
654 addr = mid_lookup_main_addr(from);
657 COPY_IP(&lq_tc->from, from);
660 COPY_IP(&lq_tc->from, addr);
662 lq_tc->ansn = ntohs(head->ansn);
666 curr = (unsigned char *)(head + 1);
670 neigh = olsr_malloc(sizeof (struct lq_tc_neighbor),
671 "LQ_TC deserialization");
673 COPY_IP(&neigh->main, curr);
676 neigh->link_quality = (double)*curr++ / 255.0;
677 neigh->neigh_link_quality = (double)*curr++ / 255.0;
681 neigh->next = lq_tc->neigh;
682 lq_tc->neigh = neigh;
687 olsr_output_lq_hello(void *para)
689 struct lq_hello_message lq_hello;
690 struct interface *outif = (struct interface *)para;
692 // create LQ_HELLO in internal format
694 create_lq_hello(&lq_hello, outif);
696 // convert internal format into transmission format, send it
698 serialize_lq_hello(&lq_hello, outif);
700 // destroy internal format
702 destroy_lq_hello(&lq_hello);
704 if(net_output_pending(outif))
709 olsr_output_lq_tc(void *para)
711 static int prev_empty = 1;
712 struct lq_tc_message lq_tc;
713 struct interface *outif = (struct interface *)para;
714 struct timeval timer;
716 // create LQ_TC in internal format
718 create_lq_tc(&lq_tc, outif);
720 // a) the message is not empty
722 if (lq_tc.neigh != NULL)
726 // convert internal format into transmission format, send it
728 serialize_lq_tc(&lq_tc, outif);
731 // b) this is the first empty message
733 else if (prev_empty == 0)
737 olsr_init_timer((olsr_u32_t)(max_tc_vtime * 3) * 1000, &timer);
738 timeradd(&now, &timer, &send_empty_tc);
742 // convert internal format into transmission format, send it
744 serialize_lq_tc(&lq_tc, outif);
747 // c) this is not the first empty message, send if timer hasn't fired
749 else if (!TIMED_OUT(&send_empty_tc))
750 serialize_lq_tc(&lq_tc, outif);
752 // destroy internal format
754 destroy_lq_tc(&lq_tc);
756 if(net_output_pending(outif) && TIMED_OUT(&fwdtimer[outif->if_nr]))
757 set_buffer_timer(outif);
761 process_lq_hello(struct lq_hello_message *lq_hello, struct interface *inif,
762 union olsr_ip_addr *from)
764 struct hello_message hello;
765 struct lq_hello_neighbor *neigh;
766 struct hello_neighbor *new_neigh;
768 // XXX - translation is ugly; everybody should use lq_hello_message :-)
770 // move the static fields from LQ_HELLO to HELLO
772 hello.vtime = lq_hello->comm.vtime;
773 hello.htime = lq_hello->htime;
775 COPY_IP(&hello.source_addr, &lq_hello->comm.orig);
777 hello.packet_seq_number = lq_hello->comm.seqno;
778 hello.hop_count = lq_hello->comm.hops;
779 hello.ttl = lq_hello->comm.ttl;
780 hello.willingness = lq_hello->will;
782 hello.neighbors = NULL;
784 // move all LQ_HELLO neighbours to HELLO
786 for (neigh = lq_hello->neigh; neigh != NULL; neigh = neigh->next)
788 // allocate HELLO neighbour
790 new_neigh = olsr_malloc(sizeof (struct hello_neighbor),
791 "LQ_HELLO translation");
795 new_neigh->status = neigh->neigh_type;
796 new_neigh->link = neigh->link_type;
797 new_neigh->link_quality = neigh->link_quality;
798 new_neigh->neigh_link_quality = neigh->neigh_link_quality;
800 COPY_IP(&new_neigh->address, &neigh->addr);
802 // queue HELLO neighbour
804 new_neigh->next = hello.neighbors;
805 hello.neighbors = new_neigh;
808 olsr_hello_tap(&hello, inif, from);
812 process_lq_tc(struct lq_tc_message *lq_tc, struct interface *inif,
813 union olsr_ip_addr *from, union olsr_message *ser)
815 struct tc_message tc;
816 struct lq_tc_neighbor *neigh;
817 struct tc_mpr_addr *new_neigh;
819 // XXX - translation is ugly; everybody should use lq_tc_message :-)
821 // move the static fields from LQ_TC to TC
823 tc.vtime = lq_tc->comm.vtime;
825 COPY_IP(&tc.source_addr, &lq_tc->from);
826 COPY_IP(&tc.originator, &lq_tc->comm.orig);
828 tc.packet_seq_number = lq_tc->comm.seqno;
829 tc.hop_count = lq_tc->comm.hops;
830 tc.ttl = lq_tc->comm.ttl;
831 tc.ansn = lq_tc->ansn;
833 tc.multipoint_relay_selector_address = NULL;
835 // move all LQ_TC neighbours to TC
837 for (neigh = lq_tc->neigh; neigh != NULL; neigh = neigh->next)
839 // allocate TC neighbour
841 new_neigh = olsr_malloc(sizeof (struct tc_mpr_addr),
842 "LQ_TC translation");
846 new_neigh->link_quality = neigh->link_quality;
847 new_neigh->neigh_link_quality = neigh->neigh_link_quality;
849 COPY_IP(&new_neigh->address, &neigh->main);
851 // queue TC neighbour
853 new_neigh->next = tc.multipoint_relay_selector_address;
854 tc.multipoint_relay_selector_address = new_neigh;
857 olsr_tc_tap(&tc, inif, from, ser);
861 olsr_input_lq_hello(union olsr_message *ser,
862 struct interface *inif,
863 union olsr_ip_addr *from)
865 struct lq_hello_message lq_hello;
867 // convert received packet from transmission format into internal format
869 deserialize_lq_hello(&lq_hello, ser);
871 // process internal format
873 process_lq_hello(&lq_hello, inif, from);
875 // destroy internal format
877 destroy_lq_hello(&lq_hello);
881 olsr_input_lq_tc(union olsr_message *ser, struct interface *inif,
882 union olsr_ip_addr *from)
884 struct lq_tc_message lq_tc;
886 // convert received packet from transmission format into internal format
888 deserialize_lq_tc(&lq_tc, ser, from);
890 // process internal format
892 process_lq_tc(&lq_tc, inif, from, ser);
894 // destroy internal format
896 destroy_lq_tc(&lq_tc);