Contiki-NG
rpl-dag.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2010, Swedish Institute of Computer Science.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the Institute nor the names of its contributors
14  * may be used to endorse or promote products derived from this software
15  * without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  * This file is part of the Contiki operating system.
30  *
31  */
32 
33 /**
34  * \file
35  * Logic for Directed Acyclic Graphs in RPL.
36  *
37  * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
38  * Contributors: George Oikonomou <oikonomou@users.sourceforge.net> (multicast)
39  */
40 
41 /**
42  * \addtogroup uip
43  * @{
44  */
45 
46 #include "contiki.h"
47 #include "net/link-stats.h"
48 #include "net/routing/rpl-classic/rpl.h"
49 #include "net/routing/rpl-classic/rpl-private.h"
50 #include "net/routing/rpl-classic/rpl-dag-root.h"
51 #include "net/ipv6/uip.h"
52 #include "net/ipv6/uip-nd6.h"
53 #include "net/ipv6/uip-ds6-nbr.h"
54 #include "net/nbr-table.h"
56 #include "lib/list.h"
57 #include "lib/memb.h"
58 #include "sys/ctimer.h"
59 
60 #include <limits.h>
61 #include <string.h>
62 
63 #define DEBUG DEBUG_NONE
64 #include "net/ipv6/uip-debug.h"
65 
66 /* A configurable function called after every RPL parent switch */
67 #ifdef RPL_CALLBACK_PARENT_SWITCH
68 void RPL_CALLBACK_PARENT_SWITCH(rpl_parent_t *old, rpl_parent_t *new);
69 #endif /* RPL_CALLBACK_PARENT_SWITCH */
70 
71 /*---------------------------------------------------------------------------*/
72 extern rpl_of_t rpl_of0, rpl_mrhof;
73 static rpl_of_t * const objective_functions[] = RPL_SUPPORTED_OFS;
74 
75 /*---------------------------------------------------------------------------*/
76 /* RPL definitions. */
77 
78 #ifndef RPL_CONF_GROUNDED
79 #define RPL_GROUNDED 0
80 #else
81 #define RPL_GROUNDED RPL_CONF_GROUNDED
82 #endif /* !RPL_CONF_GROUNDED */
83 
84 /*---------------------------------------------------------------------------*/
85 /* Per-parent RPL information */
86 NBR_TABLE_GLOBAL(rpl_parent_t, rpl_parents);
87 /*---------------------------------------------------------------------------*/
88 /* Allocate instance table. */
89 rpl_instance_t instance_table[RPL_MAX_INSTANCES];
90 rpl_instance_t *default_instance;
91 
92 /*---------------------------------------------------------------------------*/
93 void
94 rpl_print_neighbor_list(void)
95 {
96  if(default_instance != NULL && default_instance->current_dag != NULL &&
97  default_instance->of != NULL) {
98  int curr_dio_interval = default_instance->dio_intcurrent;
99  int curr_rank = default_instance->current_dag->rank;
100  rpl_parent_t *p = nbr_table_head(rpl_parents);
101  clock_time_t clock_now = clock_time();
102 
103  printf("RPL: MOP %u OCP %u rank %u dioint %u, nbr count %u\n",
104  default_instance->mop, default_instance->of->ocp, curr_rank, curr_dio_interval, uip_ds6_nbr_num());
105  while(p != NULL) {
106  const struct link_stats *stats = rpl_get_parent_link_stats(p);
107  printf("RPL: nbr %3u %5u, %5u => %5u -- %2u %c%c (last tx %u min ago)\n",
108  rpl_parent_get_ipaddr(p)->u8[15],
109  p->rank,
110  rpl_get_parent_link_metric(p),
111  rpl_rank_via_parent(p),
112  stats != NULL ? stats->freshness : 0,
113  link_stats_is_fresh(stats) ? 'f' : ' ',
114  p == default_instance->current_dag->preferred_parent ? 'p' : ' ',
115  (unsigned)((clock_now - stats->last_tx_time) / (60 * CLOCK_SECOND))
116  );
117  p = nbr_table_next(rpl_parents, p);
118  }
119  printf("RPL: end of list\n");
120  }
121 }
122 /*---------------------------------------------------------------------------*/
124 rpl_get_nbr(rpl_parent_t *parent)
125 {
126  const linkaddr_t *lladdr = rpl_get_parent_lladdr(parent);
127  if(lladdr != NULL) {
128  return nbr_table_get_from_lladdr(ds6_neighbors, lladdr);
129  } else {
130  return NULL;
131  }
132 }
133 /*---------------------------------------------------------------------------*/
134 static void
135 nbr_callback(void *ptr)
136 {
137  rpl_remove_parent(ptr);
138 }
139 
140 void
142 {
143  nbr_table_register(rpl_parents, (nbr_table_callback *)nbr_callback);
144 }
145 /*---------------------------------------------------------------------------*/
146 rpl_parent_t *
147 rpl_get_parent(uip_lladdr_t *addr)
148 {
149  rpl_parent_t *p = nbr_table_get_from_lladdr(rpl_parents, (linkaddr_t *)addr);
150  return p;
151 }
152 /*---------------------------------------------------------------------------*/
153 rpl_rank_t
154 rpl_get_parent_rank(uip_lladdr_t *addr)
155 {
156  rpl_parent_t *p = nbr_table_get_from_lladdr(rpl_parents, (linkaddr_t *)addr);
157  if(p != NULL) {
158  return p->rank;
159  } else {
160  return RPL_INFINITE_RANK;
161  }
162 }
163 /*---------------------------------------------------------------------------*/
164 uint16_t
165 rpl_get_parent_link_metric(rpl_parent_t *p)
166 {
167  if(p != NULL && p->dag != NULL) {
168  rpl_instance_t *instance = p->dag->instance;
169  if(instance != NULL && instance->of != NULL && instance->of->parent_link_metric != NULL) {
170  return instance->of->parent_link_metric(p);
171  }
172  }
173  return 0xffff;
174 }
175 /*---------------------------------------------------------------------------*/
176 rpl_rank_t
177 rpl_rank_via_parent(rpl_parent_t *p)
178 {
179  if(p != NULL && p->dag != NULL) {
180  rpl_instance_t *instance = p->dag->instance;
181  if(instance != NULL && instance->of != NULL && instance->of->rank_via_parent != NULL) {
182  return instance->of->rank_via_parent(p);
183  }
184  }
185  return RPL_INFINITE_RANK;
186 }
187 /*---------------------------------------------------------------------------*/
188 const linkaddr_t *
189 rpl_get_parent_lladdr(rpl_parent_t *p)
190 {
191  return nbr_table_get_lladdr(rpl_parents, p);
192 }
193 /*---------------------------------------------------------------------------*/
194 uip_ipaddr_t *
195 rpl_parent_get_ipaddr(rpl_parent_t *p)
196 {
197  const linkaddr_t *lladdr = rpl_get_parent_lladdr(p);
198  return uip_ds6_nbr_ipaddr_from_lladdr((uip_lladdr_t *)lladdr);
199 }
200 /*---------------------------------------------------------------------------*/
201 const struct link_stats *
202 rpl_get_parent_link_stats(rpl_parent_t *p)
203 {
204  const linkaddr_t *lladdr = rpl_get_parent_lladdr(p);
205  return link_stats_from_lladdr(lladdr);
206 }
207 /*---------------------------------------------------------------------------*/
208 int
209 rpl_parent_is_fresh(rpl_parent_t *p)
210 {
211  const struct link_stats *stats = rpl_get_parent_link_stats(p);
212  return link_stats_is_fresh(stats);
213 }
214 /*---------------------------------------------------------------------------*/
215 int
216 rpl_parent_is_reachable(rpl_parent_t *p) {
217  if(p == NULL || p->dag == NULL || p->dag->instance == NULL || p->dag->instance->of == NULL) {
218  return 0;
219  } else {
220 #if UIP_ND6_SEND_NS
221  uip_ds6_nbr_t *nbr = rpl_get_nbr(p);
222  /* Exclude links to a neighbor that is not reachable at a NUD level */
223  if(nbr == NULL || nbr->state != NBR_REACHABLE) {
224  return 0;
225  }
226 #endif /* UIP_ND6_SEND_NS */
227  /* If we don't have fresh link information, assume the parent is reachable. */
228  return !rpl_parent_is_fresh(p) || p->dag->instance->of->parent_has_usable_link(p);
229  }
230 }
231 /*---------------------------------------------------------------------------*/
232 static void
233 rpl_set_preferred_parent(rpl_dag_t *dag, rpl_parent_t *p)
234 {
235  if(dag != NULL && dag->preferred_parent != p) {
236  PRINTF("RPL: rpl_set_preferred_parent ");
237  if(p != NULL) {
238  PRINT6ADDR(rpl_parent_get_ipaddr(p));
239  } else {
240  PRINTF("NULL");
241  }
242  PRINTF(" used to be ");
243  if(dag->preferred_parent != NULL) {
244  PRINT6ADDR(rpl_parent_get_ipaddr(dag->preferred_parent));
245  } else {
246  PRINTF("NULL");
247  }
248  PRINTF("\n");
249 
250 #ifdef RPL_CALLBACK_PARENT_SWITCH
251  RPL_CALLBACK_PARENT_SWITCH(dag->preferred_parent, p);
252 #endif /* RPL_CALLBACK_PARENT_SWITCH */
253 
254  /* Always keep the preferred parent locked, so it remains in the
255  * neighbor table. */
256  nbr_table_unlock(rpl_parents, dag->preferred_parent);
257  nbr_table_lock(rpl_parents, p);
258  dag->preferred_parent = p;
259  }
260 }
261 /*---------------------------------------------------------------------------*/
262 /* Greater-than function for the lollipop counter. */
263 /*---------------------------------------------------------------------------*/
264 static int
265 lollipop_greater_than(int a, int b)
266 {
267  /* Check if we are comparing an initial value with an old value */
268  if(a > RPL_LOLLIPOP_CIRCULAR_REGION && b <= RPL_LOLLIPOP_CIRCULAR_REGION) {
269  return (RPL_LOLLIPOP_MAX_VALUE + 1 + b - a) > RPL_LOLLIPOP_SEQUENCE_WINDOWS;
270  }
271  /* Otherwise check if a > b and comparable => ok, or
272  if they have wrapped and are still comparable */
273  return (a > b && (a - b) < RPL_LOLLIPOP_SEQUENCE_WINDOWS) ||
274  (a < b && (b - a) > (RPL_LOLLIPOP_CIRCULAR_REGION + 1-
275  RPL_LOLLIPOP_SEQUENCE_WINDOWS));
276 }
277 /*---------------------------------------------------------------------------*/
278 /* Remove DAG parents with a rank that is at least the same as minimum_rank. */
279 static void
280 remove_parents(rpl_dag_t *dag, rpl_rank_t minimum_rank)
281 {
282  rpl_parent_t *p;
283 
284  PRINTF("RPL: Removing parents (minimum rank %u)\n",
285  minimum_rank);
286 
287  p = nbr_table_head(rpl_parents);
288  while(p != NULL) {
289  if(dag == p->dag && p->rank >= minimum_rank) {
290  rpl_remove_parent(p);
291  }
292  p = nbr_table_next(rpl_parents, p);
293  }
294 }
295 /*---------------------------------------------------------------------------*/
296 static void
297 nullify_parents(rpl_dag_t *dag, rpl_rank_t minimum_rank)
298 {
299  rpl_parent_t *p;
300 
301  PRINTF("RPL: Nullifying parents (minimum rank %u)\n",
302  minimum_rank);
303 
304  p = nbr_table_head(rpl_parents);
305  while(p != NULL) {
306  if(dag == p->dag && p->rank >= minimum_rank) {
307  rpl_nullify_parent(p);
308  }
309  p = nbr_table_next(rpl_parents, p);
310  }
311 }
312 /*---------------------------------------------------------------------------*/
313 static int
314 should_refresh_routes(rpl_instance_t *instance, rpl_dio_t *dio, rpl_parent_t *p)
315 {
316  /* if MOP is set to no downward routes no DAO should be sent */
317  if(instance->mop == RPL_MOP_NO_DOWNWARD_ROUTES) {
318  return 0;
319  }
320  /* check if the new DTSN is more recent */
321  return p == instance->current_dag->preferred_parent &&
322  (lollipop_greater_than(dio->dtsn, p->dtsn));
323 }
324 /*---------------------------------------------------------------------------*/
325 static int
326 acceptable_rank(rpl_dag_t *dag, rpl_rank_t rank)
327 {
328  return rank != RPL_INFINITE_RANK &&
329  ((dag->instance->max_rankinc == 0) ||
330  DAG_RANK(rank, dag->instance) <= DAG_RANK(dag->min_rank + dag->instance->max_rankinc, dag->instance));
331 }
332 /*---------------------------------------------------------------------------*/
333 static rpl_dag_t *
334 get_dag(uint8_t instance_id, uip_ipaddr_t *dag_id)
335 {
336  rpl_instance_t *instance;
337  rpl_dag_t *dag;
338  int i;
339 
340  instance = rpl_get_instance(instance_id);
341  if(instance == NULL) {
342  return NULL;
343  }
344 
345  for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; ++i) {
346  dag = &instance->dag_table[i];
347  if(dag->used && uip_ipaddr_cmp(&dag->dag_id, dag_id)) {
348  return dag;
349  }
350  }
351 
352  return NULL;
353 }
354 /*---------------------------------------------------------------------------*/
355 rpl_dag_t *
356 rpl_set_root(uint8_t instance_id, uip_ipaddr_t *dag_id)
357 {
358  rpl_dag_t *dag;
359  rpl_instance_t *instance;
360  uint8_t version;
361  int i;
362 
363  version = RPL_LOLLIPOP_INIT;
364  instance = rpl_get_instance(instance_id);
365  if(instance != NULL) {
366  for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; ++i) {
367  dag = &instance->dag_table[i];
368  if(dag->used) {
369  if(uip_ipaddr_cmp(&dag->dag_id, dag_id)) {
370  version = dag->version;
371  RPL_LOLLIPOP_INCREMENT(version);
372  }
373  if(dag == dag->instance->current_dag) {
374  PRINTF("RPL: Dropping a joined DAG when setting this node as root");
375  rpl_set_default_route(instance, NULL);
376  dag->instance->current_dag = NULL;
377  } else {
378  PRINTF("RPL: Dropping a DAG when setting this node as root");
379  }
380  rpl_free_dag(dag);
381  }
382  }
383  }
384 
385  dag = rpl_alloc_dag(instance_id, dag_id);
386  if(dag == NULL) {
387  PRINTF("RPL: Failed to allocate a DAG\n");
388  return NULL;
389  }
390 
391  instance = dag->instance;
392 
393  dag->version = version;
394  dag->joined = 1;
395  dag->grounded = RPL_GROUNDED;
396  dag->preference = RPL_PREFERENCE;
397  instance->mop = RPL_MOP_DEFAULT;
398  instance->of = rpl_find_of(RPL_OF_OCP);
399  if(instance->of == NULL) {
400  PRINTF("RPL: OF with OCP %u not supported\n", RPL_OF_OCP);
401  return NULL;
402  }
403 
404  rpl_set_preferred_parent(dag, NULL);
405 
406  memcpy(&dag->dag_id, dag_id, sizeof(dag->dag_id));
407 
408  instance->dio_intdoubl = RPL_DIO_INTERVAL_DOUBLINGS;
409  instance->dio_intmin = RPL_DIO_INTERVAL_MIN;
410  /* The current interval must differ from the minimum interval in order to
411  trigger a DIO timer reset. */
412  instance->dio_intcurrent = RPL_DIO_INTERVAL_MIN +
413  RPL_DIO_INTERVAL_DOUBLINGS;
414  instance->dio_redundancy = RPL_DIO_REDUNDANCY;
415  instance->max_rankinc = RPL_MAX_RANKINC;
416  instance->min_hoprankinc = RPL_MIN_HOPRANKINC;
417  instance->default_lifetime = RPL_DEFAULT_LIFETIME;
418  instance->lifetime_unit = RPL_DEFAULT_LIFETIME_UNIT;
419 
420  dag->rank = ROOT_RANK(instance);
421 
422  if(instance->current_dag != dag && instance->current_dag != NULL) {
423  /* Remove routes installed by DAOs. */
424  if(RPL_IS_STORING(instance)) {
425  rpl_remove_routes(instance->current_dag);
426  }
427 
428  instance->current_dag->joined = 0;
429  }
430 
431  instance->current_dag = dag;
432  instance->dtsn_out = RPL_LOLLIPOP_INIT;
433  instance->of->update_metric_container(instance);
434  default_instance = instance;
435 
436  PRINTF("RPL: Node set to be a DAG root with DAG ID ");
437  PRINT6ADDR(&dag->dag_id);
438  PRINTF("\n");
439 
440  ANNOTATE("#A root=%u\n", dag->dag_id.u8[sizeof(dag->dag_id) - 1]);
441 
442  rpl_reset_dio_timer(instance);
443 
444  return dag;
445 }
446 /*---------------------------------------------------------------------------*/
447 int
448 rpl_repair_root(uint8_t instance_id)
449 {
450  rpl_instance_t *instance;
451 
452  instance = rpl_get_instance(instance_id);
453  if(instance == NULL ||
454  instance->current_dag->rank != ROOT_RANK(instance)) {
455  PRINTF("RPL: rpl_repair_root triggered but not root\n");
456  return 0;
457  }
458  RPL_STAT(rpl_stats.root_repairs++);
459 
460  RPL_LOLLIPOP_INCREMENT(instance->current_dag->version);
461  RPL_LOLLIPOP_INCREMENT(instance->dtsn_out);
462  PRINTF("RPL: rpl_repair_root initiating global repair with version %d\n", instance->current_dag->version);
463  rpl_reset_dio_timer(instance);
464  return 1;
465 }
466 /*---------------------------------------------------------------------------*/
467 static void
468 set_ip_from_prefix(uip_ipaddr_t *ipaddr, rpl_prefix_t *prefix)
469 {
470  memset(ipaddr, 0, sizeof(uip_ipaddr_t));
471  memcpy(ipaddr, &prefix->prefix, (prefix->length + 7) / 8);
473 }
474 /*---------------------------------------------------------------------------*/
475 static void
476 check_prefix(rpl_prefix_t *last_prefix, rpl_prefix_t *new_prefix)
477 {
478  uip_ipaddr_t ipaddr;
479  uip_ds6_addr_t *rep;
480 
481  if(last_prefix != NULL && new_prefix != NULL &&
482  last_prefix->length == new_prefix->length &&
483  uip_ipaddr_prefixcmp(&last_prefix->prefix, &new_prefix->prefix, new_prefix->length) &&
484  last_prefix->flags == new_prefix->flags) {
485  /* Nothing has changed. */
486  return;
487  }
488 
489  if(last_prefix != NULL) {
490  set_ip_from_prefix(&ipaddr, last_prefix);
491  rep = uip_ds6_addr_lookup(&ipaddr);
492  if(rep != NULL) {
493  PRINTF("RPL: removing global IP address ");
494  PRINT6ADDR(&ipaddr);
495  PRINTF("\n");
496  uip_ds6_addr_rm(rep);
497  }
498  }
499 
500  if(new_prefix != NULL) {
501  set_ip_from_prefix(&ipaddr, new_prefix);
502  if(uip_ds6_addr_lookup(&ipaddr) == NULL) {
503  PRINTF("RPL: adding global IP address ");
504  PRINT6ADDR(&ipaddr);
505  PRINTF("\n");
506  uip_ds6_addr_add(&ipaddr, 0, ADDR_AUTOCONF);
507  }
508  }
509 }
510 /*---------------------------------------------------------------------------*/
511 int
512 rpl_set_prefix(rpl_dag_t *dag, uip_ipaddr_t *prefix, unsigned len)
513 {
514  rpl_prefix_t last_prefix;
515  uint8_t last_len = dag->prefix_info.length;
516 
517  if(len > 128) {
518  return 0;
519  }
520  if(dag->prefix_info.length != 0) {
521  memcpy(&last_prefix, &dag->prefix_info, sizeof(rpl_prefix_t));
522  }
523  memset(&dag->prefix_info.prefix, 0, sizeof(dag->prefix_info.prefix));
524  memcpy(&dag->prefix_info.prefix, prefix, (len + 7) / 8);
525  dag->prefix_info.length = len;
526  dag->prefix_info.flags = UIP_ND6_RA_FLAG_AUTONOMOUS;
527  PRINTF("RPL: Prefix set - will announce this in DIOs\n");
528  if(dag->rank != ROOT_RANK(dag->instance)) {
529  /* Autoconfigure an address if this node does not already have an address
530  with this prefix. Otherwise, update the prefix */
531  if(last_len == 0) {
532  PRINTF("rpl_set_prefix - prefix NULL\n");
533  check_prefix(NULL, &dag->prefix_info);
534  } else {
535  PRINTF("rpl_set_prefix - prefix NON-NULL\n");
536  check_prefix(&last_prefix, &dag->prefix_info);
537  }
538  }
539  return 1;
540 }
541 /*---------------------------------------------------------------------------*/
542 int
543 rpl_set_default_route(rpl_instance_t *instance, uip_ipaddr_t *from)
544 {
545  if(instance->def_route != NULL) {
546  PRINTF("RPL: Removing default route through ");
547  PRINT6ADDR(&instance->def_route->ipaddr);
548  PRINTF("\n");
549  uip_ds6_defrt_rm(instance->def_route);
550  instance->def_route = NULL;
551  }
552 
553  if(from != NULL) {
554  PRINTF("RPL: Adding default route through ");
555  PRINT6ADDR(from);
556  PRINTF("\n");
557  instance->def_route = uip_ds6_defrt_add(from,
558  RPL_DEFAULT_ROUTE_INFINITE_LIFETIME ? 0 : RPL_LIFETIME(instance, instance->default_lifetime));
559  if(instance->def_route == NULL) {
560  return 0;
561  }
562  }
563  return 1;
564 }
565 /*---------------------------------------------------------------------------*/
567 rpl_alloc_instance(uint8_t instance_id)
568 {
569  rpl_instance_t *instance, *end;
570 
571  for(instance = &instance_table[0], end = instance + RPL_MAX_INSTANCES;
572  instance < end; ++instance) {
573  if(instance->used == 0) {
574  memset(instance, 0, sizeof(*instance));
575  instance->instance_id = instance_id;
576  instance->def_route = NULL;
577  instance->used = 1;
578 #if RPL_WITH_PROBING
579  rpl_schedule_probing(instance);
580 #endif /* RPL_WITH_PROBING */
581  return instance;
582  }
583  }
584  return NULL;
585 }
586 /*---------------------------------------------------------------------------*/
587 rpl_dag_t *
588 rpl_alloc_dag(uint8_t instance_id, uip_ipaddr_t *dag_id)
589 {
590  rpl_dag_t *dag, *end;
591  rpl_instance_t *instance;
592 
593  instance = rpl_get_instance(instance_id);
594  if(instance == NULL) {
595  instance = rpl_alloc_instance(instance_id);
596  if(instance == NULL) {
597  RPL_STAT(rpl_stats.mem_overflows++);
598  return NULL;
599  }
600  }
601 
602  for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) {
603  if(!dag->used) {
604  memset(dag, 0, sizeof(*dag));
605  dag->used = 1;
606  dag->rank = RPL_INFINITE_RANK;
607  dag->min_rank = RPL_INFINITE_RANK;
608  dag->instance = instance;
609  return dag;
610  }
611  }
612 
613  RPL_STAT(rpl_stats.mem_overflows++);
614  return NULL;
615 }
616 /*---------------------------------------------------------------------------*/
617 void
618 rpl_set_default_instance(rpl_instance_t *instance)
619 {
620  default_instance = instance;
621 }
622 /*---------------------------------------------------------------------------*/
625 {
626  return default_instance;
627 }
628 /*---------------------------------------------------------------------------*/
629 void
630 rpl_free_instance(rpl_instance_t *instance)
631 {
632  rpl_dag_t *dag;
633  rpl_dag_t *end;
634 
635  PRINTF("RPL: Leaving the instance %u\n", instance->instance_id);
636 
637  /* Remove any DAG inside this instance */
638  for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) {
639  if(dag->used) {
640  rpl_free_dag(dag);
641  }
642  }
643 
644  rpl_set_default_route(instance, NULL);
645 
646 #if RPL_WITH_PROBING
647  ctimer_stop(&instance->probing_timer);
648 #endif /* RPL_WITH_PROBING */
649  ctimer_stop(&instance->dio_timer);
650  ctimer_stop(&instance->dao_timer);
651  ctimer_stop(&instance->dao_lifetime_timer);
652 
653  if(default_instance == instance) {
654  default_instance = NULL;
655  }
656 
657  instance->used = 0;
658 }
659 /*---------------------------------------------------------------------------*/
660 void
661 rpl_free_dag(rpl_dag_t *dag)
662 {
663  if(dag->joined) {
664  PRINTF("RPL: Leaving the DAG ");
665  PRINT6ADDR(&dag->dag_id);
666  PRINTF("\n");
667  dag->joined = 0;
668 
669  /* Remove routes installed by DAOs. */
670  if(RPL_IS_STORING(dag->instance)) {
671  rpl_remove_routes(dag);
672  }
673  /* Stop the DAO retransmit timer */
674 #if RPL_WITH_DAO_ACK
675  ctimer_stop(&dag->instance->dao_retransmit_timer);
676 #endif /* RPL_WITH_DAO_ACK */
677 
678  /* Remove autoconfigured address */
679  if((dag->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS)) {
680  check_prefix(&dag->prefix_info, NULL);
681  }
682 
683  remove_parents(dag, 0);
684  }
685  dag->used = 0;
686 }
687 /*---------------------------------------------------------------------------*/
688 rpl_parent_t *
689 rpl_add_parent(rpl_dag_t *dag, rpl_dio_t *dio, uip_ipaddr_t *addr)
690 {
691  rpl_parent_t *p = NULL;
692  /* Is the parent known by ds6? Drop this request if not.
693  * Typically, the parent is added upon receiving a DIO. */
694  const uip_lladdr_t *lladdr = uip_ds6_nbr_lladdr_from_ipaddr(addr);
695 
696  PRINTF("RPL: rpl_add_parent lladdr %p ", lladdr);
697  PRINT6ADDR(addr);
698  PRINTF("\n");
699  if(lladdr != NULL) {
700  /* Add parent in rpl_parents - again this is due to DIO */
701  p = nbr_table_add_lladdr(rpl_parents, (linkaddr_t *)lladdr,
702  NBR_TABLE_REASON_RPL_DIO, dio);
703  if(p == NULL) {
704  PRINTF("RPL: rpl_add_parent p NULL\n");
705  } else {
706  p->dag = dag;
707  p->rank = dio->rank;
708  p->dtsn = dio->dtsn;
709 #if RPL_WITH_MC
710  memcpy(&p->mc, &dio->mc, sizeof(p->mc));
711 #endif /* RPL_WITH_MC */
712  }
713  }
714 
715  return p;
716 }
717 /*---------------------------------------------------------------------------*/
718 static rpl_parent_t *
719 find_parent_any_dag_any_instance(uip_ipaddr_t *addr)
720 {
721  uip_ds6_nbr_t *ds6_nbr = uip_ds6_nbr_lookup(addr);
722  const uip_lladdr_t *lladdr = uip_ds6_nbr_get_ll(ds6_nbr);
723  return nbr_table_get_from_lladdr(rpl_parents, (linkaddr_t *)lladdr);
724 }
725 /*---------------------------------------------------------------------------*/
726 rpl_parent_t *
727 rpl_find_parent(rpl_dag_t *dag, uip_ipaddr_t *addr)
728 {
729  rpl_parent_t *p = find_parent_any_dag_any_instance(addr);
730  if(p != NULL && p->dag == dag) {
731  return p;
732  } else {
733  return NULL;
734  }
735 }
736 /*---------------------------------------------------------------------------*/
737 static rpl_dag_t *
738 find_parent_dag(rpl_instance_t *instance, uip_ipaddr_t *addr)
739 {
740  rpl_parent_t *p = find_parent_any_dag_any_instance(addr);
741  if(p != NULL) {
742  return p->dag;
743  } else {
744  return NULL;
745  }
746 }
747 /*---------------------------------------------------------------------------*/
748 rpl_parent_t *
749 rpl_find_parent_any_dag(rpl_instance_t *instance, uip_ipaddr_t *addr)
750 {
751  rpl_parent_t *p = find_parent_any_dag_any_instance(addr);
752  if(p && p->dag && p->dag->instance == instance) {
753  return p;
754  } else {
755  return NULL;
756  }
757 }
758 /*---------------------------------------------------------------------------*/
759 rpl_dag_t *
760 rpl_select_dag(rpl_instance_t *instance, rpl_parent_t *p)
761 {
762  rpl_parent_t *last_parent;
763  rpl_dag_t *dag, *end, *best_dag;
764  rpl_rank_t old_rank;
765 
766  old_rank = instance->current_dag->rank;
767  last_parent = instance->current_dag->preferred_parent;
768 
769  if(instance->current_dag->rank != ROOT_RANK(instance)) {
770  rpl_select_parent(p->dag);
771  }
772 
773  best_dag = NULL;
774  for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) {
775  if(dag->used && dag->preferred_parent != NULL && dag->preferred_parent->rank != RPL_INFINITE_RANK) {
776  if(best_dag == NULL) {
777  best_dag = dag;
778  } else {
779  best_dag = instance->of->best_dag(best_dag, dag);
780  }
781  }
782  }
783 
784  if(best_dag == NULL) {
785  /* No parent found: the calling function handle this problem. */
786  return NULL;
787  }
788 
789  if(instance->current_dag != best_dag) {
790  /* Remove routes installed by DAOs. */
791  if(RPL_IS_STORING(instance)) {
792  rpl_remove_routes(instance->current_dag);
793  }
794 
795  PRINTF("RPL: New preferred DAG: ");
796  PRINT6ADDR(&best_dag->dag_id);
797  PRINTF("\n");
798 
799  if(best_dag->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) {
800  check_prefix(&instance->current_dag->prefix_info, &best_dag->prefix_info);
801  } else if(instance->current_dag->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) {
802  check_prefix(&instance->current_dag->prefix_info, NULL);
803  }
804 
805  best_dag->joined = 1;
806  instance->current_dag->joined = 0;
807  instance->current_dag = best_dag;
808  }
809 
810  instance->of->update_metric_container(instance);
811  /* Update the DAG rank. */
812  best_dag->rank = rpl_rank_via_parent(best_dag->preferred_parent);
813  if(last_parent == NULL || best_dag->rank < best_dag->min_rank) {
814  /* This is a slight departure from RFC6550: if we had no preferred parent before,
815  * reset min_rank. This helps recovering from temporary bad link conditions. */
816  best_dag->min_rank = best_dag->rank;
817  }
818 
819  if(!acceptable_rank(best_dag, best_dag->rank)) {
820  PRINTF("RPL: New rank unacceptable!\n");
821  rpl_set_preferred_parent(instance->current_dag, NULL);
822  if(RPL_IS_STORING(instance) && last_parent != NULL) {
823  /* Send a No-Path DAO to the removed preferred parent. */
824  dao_output(last_parent, RPL_ZERO_LIFETIME);
825  }
826  return NULL;
827  }
828 
829  if(best_dag->preferred_parent != last_parent) {
830  rpl_set_default_route(instance, rpl_parent_get_ipaddr(best_dag->preferred_parent));
831  PRINTF("RPL: Changed preferred parent, rank changed from %u to %u\n",
832  (unsigned)old_rank, best_dag->rank);
833  RPL_STAT(rpl_stats.parent_switch++);
834  if(RPL_IS_STORING(instance)) {
835  if(last_parent != NULL) {
836  /* Send a No-Path DAO to the removed preferred parent. */
837  dao_output(last_parent, RPL_ZERO_LIFETIME);
838  }
839  /* Trigger DAO transmission from immediate children.
840  * Only for storing mode, see RFC6550 section 9.6. */
841  RPL_LOLLIPOP_INCREMENT(instance->dtsn_out);
842  }
843  /* The DAO parent set changed - schedule a DAO transmission. */
844  rpl_schedule_dao(instance);
845  rpl_reset_dio_timer(instance);
846 #if DEBUG
847  rpl_print_neighbor_list();
848 #endif
849  } else if(best_dag->rank != old_rank) {
850  PRINTF("RPL: Preferred parent update, rank changed from %u to %u\n",
851  (unsigned)old_rank, best_dag->rank);
852  }
853  return best_dag;
854 }
855 /*---------------------------------------------------------------------------*/
856 static rpl_parent_t *
857 best_parent(rpl_dag_t *dag, int fresh_only)
858 {
859  rpl_parent_t *p;
860  rpl_of_t *of;
861  rpl_parent_t *best = NULL;
862 
863  if(dag == NULL || dag->instance == NULL || dag->instance->of == NULL) {
864  return NULL;
865  }
866 
867  of = dag->instance->of;
868  /* Search for the best parent according to the OF */
869  for(p = nbr_table_head(rpl_parents); p != NULL; p = nbr_table_next(rpl_parents, p)) {
870 
871  /* Exclude parents from other DAGs or announcing an infinite rank */
872  if(p->dag != dag || p->rank == RPL_INFINITE_RANK || p->rank < ROOT_RANK(dag->instance)) {
873  if(p->rank < ROOT_RANK(dag->instance)) {
874  PRINTF("RPL: Parent has invalid rank\n");
875  }
876  continue;
877  }
878 
879  if(fresh_only && !rpl_parent_is_fresh(p)) {
880  /* Filter out non-fresh parents if fresh_only is set */
881  continue;
882  }
883 
884 #if UIP_ND6_SEND_NS
885  {
886  uip_ds6_nbr_t *nbr = rpl_get_nbr(p);
887  /* Exclude links to a neighbor that is not reachable at a NUD level */
888  if(nbr == NULL || nbr->state != NBR_REACHABLE) {
889  continue;
890  }
891  }
892 #endif /* UIP_ND6_SEND_NS */
893 
894  /* Now we have an acceptable parent, check if it is the new best */
895  best = of->best_parent(best, p);
896  }
897 
898  return best;
899 }
900 /*---------------------------------------------------------------------------*/
901 rpl_parent_t *
902 rpl_select_parent(rpl_dag_t *dag)
903 {
904  /* Look for best parent (regardless of freshness) */
905  rpl_parent_t *best = best_parent(dag, 0);
906 
907  if(best != NULL) {
908 #if RPL_WITH_PROBING
909  if(rpl_parent_is_fresh(best)) {
910  rpl_set_preferred_parent(dag, best);
911  /* Unschedule any already scheduled urgent probing */
912  dag->instance->urgent_probing_target = NULL;
913  } else {
914  /* The best is not fresh. Look for the best fresh now. */
915  rpl_parent_t *best_fresh = best_parent(dag, 1);
916  if(best_fresh == NULL) {
917  /* No fresh parent around, use best (non-fresh) */
918  rpl_set_preferred_parent(dag, best);
919  } else {
920  /* Use best fresh */
921  rpl_set_preferred_parent(dag, best_fresh);
922  }
923  /* Probe the best parent shortly in order to get a fresh estimate */
924  dag->instance->urgent_probing_target = best;
925  rpl_schedule_probing_now(dag->instance);
926  }
927 #else /* RPL_WITH_PROBING */
928  rpl_set_preferred_parent(dag, best);
929  dag->rank = rpl_rank_via_parent(dag->preferred_parent);
930 #endif /* RPL_WITH_PROBING */
931  } else {
932  rpl_set_preferred_parent(dag, NULL);
933  }
934 
935  dag->rank = rpl_rank_via_parent(dag->preferred_parent);
936  return dag->preferred_parent;
937 }
938 /*---------------------------------------------------------------------------*/
939 void
940 rpl_remove_parent(rpl_parent_t *parent)
941 {
942  PRINTF("RPL: Removing parent ");
943  PRINT6ADDR(rpl_parent_get_ipaddr(parent));
944  PRINTF("\n");
945 
946  rpl_nullify_parent(parent);
947 
948  nbr_table_remove(rpl_parents, parent);
949 }
950 /*---------------------------------------------------------------------------*/
951 void
952 rpl_nullify_parent(rpl_parent_t *parent)
953 {
954  rpl_dag_t *dag = parent->dag;
955  /* This function can be called when the preferred parent is NULL, so we
956  need to handle this condition in order to trigger uip_ds6_defrt_rm. */
957  if(parent == dag->preferred_parent || dag->preferred_parent == NULL) {
958  dag->rank = RPL_INFINITE_RANK;
959  if(dag->joined) {
960  if(dag->instance->def_route != NULL) {
961  PRINTF("RPL: Removing default route ");
962  PRINT6ADDR(rpl_parent_get_ipaddr(parent));
963  PRINTF("\n");
964  uip_ds6_defrt_rm(dag->instance->def_route);
965  dag->instance->def_route = NULL;
966  }
967  /* Send No-Path DAO only when nullifying preferred parent */
968  if(parent == dag->preferred_parent) {
969  if(RPL_IS_STORING(dag->instance)) {
970  dao_output(parent, RPL_ZERO_LIFETIME);
971  }
972  rpl_set_preferred_parent(dag, NULL);
973  }
974  }
975  }
976 
977  PRINTF("RPL: Nullifying parent ");
978  PRINT6ADDR(rpl_parent_get_ipaddr(parent));
979  PRINTF("\n");
980 }
981 /*---------------------------------------------------------------------------*/
982 void
983 rpl_move_parent(rpl_dag_t *dag_src, rpl_dag_t *dag_dst, rpl_parent_t *parent)
984 {
985  if(parent == dag_src->preferred_parent) {
986  rpl_set_preferred_parent(dag_src, NULL);
987  dag_src->rank = RPL_INFINITE_RANK;
988  if(dag_src->joined && dag_src->instance->def_route != NULL) {
989  PRINTF("RPL: Removing default route ");
990  PRINT6ADDR(rpl_parent_get_ipaddr(parent));
991  PRINTF("\n");
992  PRINTF("rpl_move_parent\n");
993  uip_ds6_defrt_rm(dag_src->instance->def_route);
994  dag_src->instance->def_route = NULL;
995  }
996  } else if(dag_src->joined) {
997  if(RPL_IS_STORING(dag_src->instance)) {
998  /* Remove uIPv6 routes that have this parent as the next hop. */
999  rpl_remove_routes_by_nexthop(rpl_parent_get_ipaddr(parent), dag_src);
1000  }
1001  }
1002 
1003  PRINTF("RPL: Moving parent ");
1004  PRINT6ADDR(rpl_parent_get_ipaddr(parent));
1005  PRINTF("\n");
1006 
1007  parent->dag = dag_dst;
1008 }
1009 /*---------------------------------------------------------------------------*/
1010 int
1012 {
1013  return rpl_get_any_dag() != NULL;
1014 }
1015 /*---------------------------------------------------------------------------*/
1016 int
1018 {
1019  int i;
1020  if(rpl_dag_root_is_root()) {
1021  return 1; /* We are the root, and know the route to ourself */
1022  }
1023  for(i = 0; i < RPL_MAX_INSTANCES; ++i) {
1024  if(instance_table[i].used && instance_table[i].has_downward_route) {
1025  return 1;
1026  }
1027  }
1028  return 0;
1029 }
1030 /*---------------------------------------------------------------------------*/
1031 rpl_dag_t *
1032 rpl_get_dag(const uip_ipaddr_t *addr)
1033 {
1034  int i, j;
1035 
1036  for(i = 0; i < RPL_MAX_INSTANCES; ++i) {
1037  if(instance_table[i].used) {
1038  for(j = 0; j < RPL_MAX_DAG_PER_INSTANCE; ++j) {
1039  if(instance_table[i].dag_table[j].joined
1040  && uip_ipaddr_prefixcmp(&instance_table[i].dag_table[j].dag_id, addr,
1041  instance_table[i].dag_table[j].prefix_info.length)) {
1042  return &instance_table[i].dag_table[j];
1043  }
1044  }
1045  }
1046  }
1047  return NULL;
1048 }
1049 /*---------------------------------------------------------------------------*/
1050 rpl_dag_t *
1052 {
1053  int i;
1054 
1055  for(i = 0; i < RPL_MAX_INSTANCES; ++i) {
1056  if(instance_table[i].used && instance_table[i].current_dag->joined) {
1057  return instance_table[i].current_dag;
1058  }
1059  }
1060  return NULL;
1061 }
1062 /*---------------------------------------------------------------------------*/
1064 rpl_get_instance(uint8_t instance_id)
1065 {
1066  int i;
1067 
1068  for(i = 0; i < RPL_MAX_INSTANCES; ++i) {
1069  if(instance_table[i].used && instance_table[i].instance_id == instance_id) {
1070  return &instance_table[i];
1071  }
1072  }
1073  return NULL;
1074 }
1075 /*---------------------------------------------------------------------------*/
1076 rpl_of_t *
1077 rpl_find_of(rpl_ocp_t ocp)
1078 {
1079  unsigned int i;
1080 
1081  for(i = 0;
1082  i < sizeof(objective_functions) / sizeof(objective_functions[0]);
1083  i++) {
1084  if(objective_functions[i]->ocp == ocp) {
1085  return objective_functions[i];
1086  }
1087  }
1088 
1089  return NULL;
1090 }
1091 /*---------------------------------------------------------------------------*/
1092 void
1093 rpl_join_instance(uip_ipaddr_t *from, rpl_dio_t *dio)
1094 {
1095  rpl_instance_t *instance;
1096  rpl_dag_t *dag;
1097  rpl_parent_t *p;
1098  rpl_of_t *of;
1099 
1100  if((!RPL_WITH_NON_STORING && dio->mop == RPL_MOP_NON_STORING)
1101  || (!RPL_WITH_STORING && (dio->mop == RPL_MOP_STORING_NO_MULTICAST
1102  || dio->mop == RPL_MOP_STORING_MULTICAST))) {
1103  PRINTF("RPL: DIO advertising a non-supported MOP %u\n", dio->mop);
1104  return;
1105  }
1106 
1107  /* Determine the objective function by using the
1108  objective code point of the DIO. */
1109  of = rpl_find_of(dio->ocp);
1110  if(of == NULL) {
1111  PRINTF("RPL: DIO for DAG instance %u does not specify a supported OF: %u\n",
1112  dio->instance_id, dio->ocp);
1113  return;
1114  }
1115 
1116  dag = rpl_alloc_dag(dio->instance_id, &dio->dag_id);
1117  if(dag == NULL) {
1118  PRINTF("RPL: Failed to allocate a DAG object!\n");
1119  return;
1120  }
1121 
1122  instance = dag->instance;
1123 
1124  p = rpl_add_parent(dag, dio, from);
1125  PRINTF("RPL: Adding ");
1126  PRINT6ADDR(from);
1127  PRINTF(" as a parent: ");
1128  if(p == NULL) {
1129  PRINTF("failed\n");
1130  instance->used = 0;
1131  return;
1132  }
1133  p->dtsn = dio->dtsn;
1134  PRINTF("succeeded\n");
1135 
1136  /* Autoconfigure an address if this node does not already have an address
1137  with this prefix. */
1138  if(dio->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) {
1139  check_prefix(NULL, &dio->prefix_info);
1140  }
1141 
1142  dag->joined = 1;
1143  dag->preference = dio->preference;
1144  dag->grounded = dio->grounded;
1145  dag->version = dio->version;
1146 
1147  instance->of = of;
1148  instance->mop = dio->mop;
1149  instance->mc.type = dio->mc.type;
1150  instance->mc.flags = dio->mc.flags;
1151  instance->mc.aggr = dio->mc.aggr;
1152  instance->mc.prec = dio->mc.prec;
1153  instance->current_dag = dag;
1154  instance->dtsn_out = RPL_LOLLIPOP_INIT;
1155 
1156  instance->max_rankinc = dio->dag_max_rankinc;
1157  instance->min_hoprankinc = dio->dag_min_hoprankinc;
1158  instance->dio_intdoubl = dio->dag_intdoubl;
1159  instance->dio_intmin = dio->dag_intmin;
1160  instance->dio_intcurrent = instance->dio_intmin + instance->dio_intdoubl;
1161  instance->dio_redundancy = dio->dag_redund;
1162  instance->default_lifetime = dio->default_lifetime;
1163  instance->lifetime_unit = dio->lifetime_unit;
1164 
1165  memcpy(&dag->dag_id, &dio->dag_id, sizeof(dio->dag_id));
1166 
1167  /* Copy prefix information from the DIO into the DAG object. */
1168  memcpy(&dag->prefix_info, &dio->prefix_info, sizeof(rpl_prefix_t));
1169 
1170  rpl_set_preferred_parent(dag, p);
1171  instance->of->update_metric_container(instance);
1172  dag->rank = rpl_rank_via_parent(p);
1173  /* So far this is the lowest rank we are aware of. */
1174  dag->min_rank = dag->rank;
1175 
1176  if(default_instance == NULL) {
1177  default_instance = instance;
1178  }
1179 
1180  PRINTF("RPL: Joined DAG with instance ID %u, rank %hu, DAG ID ",
1181  dio->instance_id, dag->rank);
1182  PRINT6ADDR(&dag->dag_id);
1183  PRINTF("\n");
1184 
1185  ANNOTATE("#A join=%u\n", dag->dag_id.u8[sizeof(dag->dag_id) - 1]);
1186 
1187  rpl_reset_dio_timer(instance);
1188  rpl_set_default_route(instance, from);
1189 
1190  if(instance->mop != RPL_MOP_NO_DOWNWARD_ROUTES) {
1191  rpl_schedule_dao(instance);
1192  } else {
1193  PRINTF("RPL: The DIO does not meet the prerequisites for sending a DAO\n");
1194  }
1195 
1196  instance->of->reset(dag);
1197 }
1198 
1199 #if RPL_MAX_DAG_PER_INSTANCE > 1
1200 /*---------------------------------------------------------------------------*/
1201 rpl_dag_t *
1202 rpl_add_dag(uip_ipaddr_t *from, rpl_dio_t *dio)
1203 {
1204  rpl_instance_t *instance;
1205  rpl_dag_t *dag, *previous_dag;
1206  rpl_parent_t *p;
1207  rpl_of_t *of;
1208 
1209  dag = rpl_alloc_dag(dio->instance_id, &dio->dag_id);
1210  if(dag == NULL) {
1211  PRINTF("RPL: Failed to allocate a DAG object!\n");
1212  return NULL;
1213  }
1214 
1215  instance = dag->instance;
1216 
1217  previous_dag = find_parent_dag(instance, from);
1218  if(previous_dag == NULL) {
1219  PRINTF("RPL: Adding ");
1220  PRINT6ADDR(from);
1221  PRINTF(" as a parent: ");
1222  p = rpl_add_parent(dag, dio, from);
1223  if(p == NULL) {
1224  PRINTF("failed\n");
1225  dag->used = 0;
1226  return NULL;
1227  }
1228  PRINTF("succeeded\n");
1229  } else {
1230  p = rpl_find_parent(previous_dag, from);
1231  if(p != NULL) {
1232  rpl_move_parent(previous_dag, dag, p);
1233  }
1234  }
1235  p->rank = dio->rank;
1236 
1237  /* Determine the objective function by using the
1238  objective code point of the DIO. */
1239  of = rpl_find_of(dio->ocp);
1240  if(of != instance->of ||
1241  instance->mop != dio->mop ||
1242  instance->max_rankinc != dio->dag_max_rankinc ||
1243  instance->min_hoprankinc != dio->dag_min_hoprankinc ||
1244  instance->dio_intdoubl != dio->dag_intdoubl ||
1245  instance->dio_intmin != dio->dag_intmin ||
1246  instance->dio_redundancy != dio->dag_redund ||
1247  instance->default_lifetime != dio->default_lifetime ||
1248  instance->lifetime_unit != dio->lifetime_unit) {
1249  PRINTF("RPL: DIO for DAG instance %u incompatible with previous DIO\n",
1250  dio->instance_id);
1251  rpl_remove_parent(p);
1252  dag->used = 0;
1253  return NULL;
1254  }
1255 
1256  dag->used = 1;
1257  dag->grounded = dio->grounded;
1258  dag->preference = dio->preference;
1259  dag->version = dio->version;
1260 
1261  memcpy(&dag->dag_id, &dio->dag_id, sizeof(dio->dag_id));
1262 
1263  /* copy prefix information into the dag */
1264  memcpy(&dag->prefix_info, &dio->prefix_info, sizeof(rpl_prefix_t));
1265 
1266  rpl_set_preferred_parent(dag, p);
1267  dag->rank = rpl_rank_via_parent(p);
1268  dag->min_rank = dag->rank; /* So far this is the lowest rank we know of. */
1269 
1270  PRINTF("RPL: Joined DAG with instance ID %u, rank %hu, DAG ID ",
1271  dio->instance_id, dag->rank);
1272  PRINT6ADDR(&dag->dag_id);
1273  PRINTF("\n");
1274 
1275  ANNOTATE("#A join=%u\n", dag->dag_id.u8[sizeof(dag->dag_id) - 1]);
1276 
1277  rpl_process_parent_event(instance, p);
1278  p->dtsn = dio->dtsn;
1279 
1280  return dag;
1281 }
1282 #endif /* RPL_MAX_DAG_PER_INSTANCE > 1 */
1283 
1284 /*---------------------------------------------------------------------------*/
1285 static void
1286 global_repair(uip_ipaddr_t *from, rpl_dag_t *dag, rpl_dio_t *dio)
1287 {
1288  rpl_parent_t *p;
1289 
1290  remove_parents(dag, 0);
1291  dag->version = dio->version;
1292 
1293  /* copy parts of the configuration so that it propagates in the network */
1294  dag->instance->dio_intdoubl = dio->dag_intdoubl;
1295  dag->instance->dio_intmin = dio->dag_intmin;
1296  dag->instance->dio_redundancy = dio->dag_redund;
1297  dag->instance->default_lifetime = dio->default_lifetime;
1298  dag->instance->lifetime_unit = dio->lifetime_unit;
1299 
1300  dag->instance->of->reset(dag);
1301  dag->min_rank = RPL_INFINITE_RANK;
1302  RPL_LOLLIPOP_INCREMENT(dag->instance->dtsn_out);
1303 
1304  p = rpl_add_parent(dag, dio, from);
1305  if(p == NULL) {
1306  PRINTF("RPL: Failed to add a parent during the global repair\n");
1307  dag->rank = RPL_INFINITE_RANK;
1308  } else {
1309  dag->rank = rpl_rank_via_parent(p);
1310  dag->min_rank = dag->rank;
1311  PRINTF("RPL: rpl_process_parent_event global repair\n");
1312  rpl_process_parent_event(dag->instance, p);
1313  }
1314 
1315  PRINTF("RPL: Participating in a global repair (version=%u, rank=%hu)\n",
1316  dag->version, dag->rank);
1317 
1318  RPL_STAT(rpl_stats.global_repairs++);
1319 }
1320 
1321 /*---------------------------------------------------------------------------*/
1322 void
1324 {
1325  int i;
1326 
1327  if(instance == NULL) {
1328  PRINTF("RPL: local repair requested for instance NULL\n");
1329  return;
1330  }
1331  PRINTF("RPL: Starting a local instance repair\n");
1332  for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; i++) {
1333  if(instance->dag_table[i].used) {
1334  instance->dag_table[i].rank = RPL_INFINITE_RANK;
1335  nullify_parents(&instance->dag_table[i], 0);
1336  }
1337  }
1338 
1339  /* no downward route anymore */
1340  instance->has_downward_route = 0;
1341 #if RPL_WITH_DAO_ACK
1342  ctimer_stop(&instance->dao_retransmit_timer);
1343 #endif /* RPL_WITH_DAO_ACK */
1344 
1345  rpl_reset_dio_timer(instance);
1346  if(RPL_IS_STORING(instance)) {
1347  /* Request refresh of DAO registrations next DIO. Only for storing mode. In
1348  * non-storing mode, non-root nodes increment DTSN only on when their parent do,
1349  * or on global repair (see RFC6550 section 9.6.) */
1350  RPL_LOLLIPOP_INCREMENT(instance->dtsn_out);
1351  }
1352 
1353  RPL_STAT(rpl_stats.local_repairs++);
1354 }
1355 /*---------------------------------------------------------------------------*/
1356 void
1357 rpl_recalculate_ranks(void)
1358 {
1359  rpl_parent_t *p;
1360 
1361  /*
1362  * We recalculate ranks when we receive feedback from the system rather
1363  * than RPL protocol messages. This periodical recalculation is called
1364  * from a timer in order to keep the stack depth reasonably low.
1365  */
1366  p = nbr_table_head(rpl_parents);
1367  while(p != NULL) {
1368  if(p->dag != NULL && p->dag->instance && (p->flags & RPL_PARENT_FLAG_UPDATED)) {
1369  p->flags &= ~RPL_PARENT_FLAG_UPDATED;
1370  PRINTF("RPL: rpl_process_parent_event recalculate_ranks\n");
1371  if(!rpl_process_parent_event(p->dag->instance, p)) {
1372  PRINTF("RPL: A parent was dropped\n");
1373  }
1374  }
1375  p = nbr_table_next(rpl_parents, p);
1376  }
1377 }
1378 /*---------------------------------------------------------------------------*/
1379 int
1380 rpl_process_parent_event(rpl_instance_t *instance, rpl_parent_t *p)
1381 {
1382  int return_value;
1383  rpl_parent_t *last_parent = instance->current_dag->preferred_parent;
1384 
1385 #if DEBUG
1386  rpl_rank_t old_rank;
1387  old_rank = instance->current_dag->rank;
1388 #endif /* DEBUG */
1389 
1390  return_value = 1;
1391 
1392  if(RPL_IS_STORING(instance)
1393  && uip_ds6_route_is_nexthop(rpl_parent_get_ipaddr(p))
1394  && !rpl_parent_is_reachable(p) && instance->mop > RPL_MOP_NON_STORING) {
1395  PRINTF("RPL: Unacceptable link %u, removing routes via: ", rpl_get_parent_link_metric(p));
1396  PRINT6ADDR(rpl_parent_get_ipaddr(p));
1397  PRINTF("\n");
1398  rpl_remove_routes_by_nexthop(rpl_parent_get_ipaddr(p), p->dag);
1399  }
1400 
1401  if(!acceptable_rank(p->dag, p->rank)) {
1402  /* The candidate parent is no longer valid: the rank increase resulting
1403  from the choice of it as a parent would be too high. */
1404  PRINTF("RPL: Unacceptable rank %u (Current min %u, MaxRankInc %u)\n", (unsigned)p->rank,
1405  p->dag->min_rank, p->dag->instance->max_rankinc);
1406  rpl_nullify_parent(p);
1407  if(p != instance->current_dag->preferred_parent) {
1408  return 0;
1409  } else {
1410  return_value = 0;
1411  }
1412  }
1413 
1414  if(rpl_select_dag(instance, p) == NULL) {
1415  if(last_parent != NULL) {
1416  /* No suitable parent anymore; trigger a local repair. */
1417  PRINTF("RPL: No parents found in any DAG\n");
1418  rpl_local_repair(instance);
1419  return 0;
1420  }
1421  }
1422 
1423 #if DEBUG
1424  if(DAG_RANK(old_rank, instance) != DAG_RANK(instance->current_dag->rank, instance)) {
1425  PRINTF("RPL: Moving in the instance from rank %hu to %hu\n",
1426  DAG_RANK(old_rank, instance), DAG_RANK(instance->current_dag->rank, instance));
1427  if(instance->current_dag->rank != RPL_INFINITE_RANK) {
1428  PRINTF("RPL: The preferred parent is ");
1429  PRINT6ADDR(rpl_parent_get_ipaddr(instance->current_dag->preferred_parent));
1430  PRINTF(" (rank %u)\n",
1431  (unsigned)DAG_RANK(instance->current_dag->preferred_parent->rank, instance));
1432  } else {
1433  PRINTF("RPL: We don't have any parent");
1434  }
1435  }
1436 #endif /* DEBUG */
1437 
1438  return return_value;
1439 }
1440 /*---------------------------------------------------------------------------*/
1441 static int
1442 add_nbr_from_dio(uip_ipaddr_t *from, rpl_dio_t *dio)
1443 {
1444  /* add this to the neighbor cache if not already there */
1445  if(rpl_icmp6_update_nbr_table(from, NBR_TABLE_REASON_RPL_DIO, dio) == NULL) {
1446  PRINTF("RPL: Out of memory, dropping DIO from ");
1447  PRINT6ADDR(from);
1448  PRINTF("\n");
1449  return 0;
1450  }
1451  return 1;
1452 }
1453 /*---------------------------------------------------------------------------*/
1454 void
1455 rpl_process_dio(uip_ipaddr_t *from, rpl_dio_t *dio)
1456 {
1457  rpl_instance_t *instance;
1458  rpl_dag_t *dag, *previous_dag;
1459  rpl_parent_t *p;
1460 
1461 #if RPL_WITH_MULTICAST
1462  /* If the root is advertising MOP 2 but we support MOP 3 we can still join
1463  * In that scenario, we suppress DAOs for multicast targets */
1464  if(dio->mop < RPL_MOP_STORING_NO_MULTICAST) {
1465 #else
1466  if(dio->mop != RPL_MOP_DEFAULT) {
1467 #endif
1468  PRINTF("RPL: Ignoring a DIO with an unsupported MOP: %d\n", dio->mop);
1469  return;
1470  }
1471 
1472  dag = get_dag(dio->instance_id, &dio->dag_id);
1473  instance = rpl_get_instance(dio->instance_id);
1474 
1475  if(dag != NULL && instance != NULL) {
1476  if(lollipop_greater_than(dio->version, dag->version)) {
1477  if(dag->rank == ROOT_RANK(instance)) {
1478  PRINTF("RPL: Root received inconsistent DIO version number (current: %u, received: %u)\n", dag->version, dio->version);
1479  dag->version = dio->version;
1480  RPL_LOLLIPOP_INCREMENT(dag->version);
1481  rpl_reset_dio_timer(instance);
1482  } else {
1483  PRINTF("RPL: Global repair\n");
1484  if(dio->prefix_info.length != 0) {
1485  if(dio->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) {
1486  PRINTF("RPL: Prefix announced in DIO\n");
1487  rpl_set_prefix(dag, &dio->prefix_info.prefix, dio->prefix_info.length);
1488  }
1489  }
1490  global_repair(from, dag, dio);
1491  }
1492  return;
1493  }
1494 
1495  if(lollipop_greater_than(dag->version, dio->version)) {
1496  /* The DIO sender is on an older version of the DAG. */
1497  PRINTF("RPL: old version received => inconsistency detected\n");
1498  if(dag->joined) {
1499  rpl_reset_dio_timer(instance);
1500  return;
1501  }
1502  }
1503  }
1504 
1505  if(instance == NULL) {
1506  PRINTF("RPL: New instance detected (ID=%u): Joining...\n", dio->instance_id);
1507  if(add_nbr_from_dio(from, dio)) {
1508  rpl_join_instance(from, dio);
1509  } else {
1510  PRINTF("RPL: Not joining since could not add parent\n");
1511  }
1512  return;
1513  }
1514 
1515  if(instance->current_dag->rank == ROOT_RANK(instance) && instance->current_dag != dag) {
1516  PRINTF("RPL: Root ignored DIO for different DAG\n");
1517  return;
1518  }
1519 
1520  if(dag == NULL) {
1521 #if RPL_MAX_DAG_PER_INSTANCE > 1
1522  PRINTF("RPL: Adding new DAG to known instance.\n");
1523  if(!add_nbr_from_dio(from, dio)) {
1524  PRINTF("RPL: Could not add new DAG, could not add parent\n");
1525  return;
1526  }
1527  dag = rpl_add_dag(from, dio);
1528  if(dag == NULL) {
1529  PRINTF("RPL: Failed to add DAG.\n");
1530  return;
1531  }
1532 #else /* RPL_MAX_DAG_PER_INSTANCE > 1 */
1533  PRINTF("RPL: Only one instance supported.\n");
1534  return;
1535 #endif /* RPL_MAX_DAG_PER_INSTANCE > 1 */
1536  }
1537 
1538 
1539  if(dio->rank < ROOT_RANK(instance)) {
1540  PRINTF("RPL: Ignoring DIO with too low rank: %u\n",
1541  (unsigned)dio->rank);
1542  return;
1543  }
1544 
1545  /* Prefix Information Option treated to add new prefix */
1546  if(dio->prefix_info.length != 0) {
1547  if(dio->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) {
1548  PRINTF("RPL: Prefix announced in DIO\n");
1549  rpl_set_prefix(dag, &dio->prefix_info.prefix, dio->prefix_info.length);
1550  }
1551  }
1552 
1553  if(!add_nbr_from_dio(from, dio)) {
1554  PRINTF("RPL: Could not add parent based on DIO\n");
1555  return;
1556  }
1557 
1558  if(dag->rank == ROOT_RANK(instance)) {
1559  if(dio->rank != RPL_INFINITE_RANK) {
1560  instance->dio_counter++;
1561  }
1562  return;
1563  }
1564 
1565  /* The DIO comes from a valid DAG, we can refresh its lifetime */
1566  dag->lifetime = (1UL << (instance->dio_intmin + instance->dio_intdoubl)) * RPL_DAG_LIFETIME / 1000;
1567  PRINTF("Set dag ");
1568  PRINT6ADDR(&dag->dag_id);
1569  PRINTF(" lifetime to %ld\n", dag->lifetime);
1570 
1571  /*
1572  * At this point, we know that this DIO pertains to a DAG that
1573  * we are already part of. We consider the sender of the DIO to be
1574  * a candidate parent, and let rpl_process_parent_event decide
1575  * whether to keep it in the set.
1576  */
1577 
1578  p = rpl_find_parent(dag, from);
1579  if(p == NULL) {
1580  previous_dag = find_parent_dag(instance, from);
1581  if(previous_dag == NULL) {
1582  /* Add the DIO sender as a candidate parent. */
1583  p = rpl_add_parent(dag, dio, from);
1584  if(p == NULL) {
1585  PRINTF("RPL: Failed to add a new parent (");
1586  PRINT6ADDR(from);
1587  PRINTF(")\n");
1588  return;
1589  }
1590  PRINTF("RPL: New candidate parent with rank %u: ", (unsigned)p->rank);
1591  PRINT6ADDR(from);
1592  PRINTF("\n");
1593  } else {
1594  p = rpl_find_parent(previous_dag, from);
1595  if(p != NULL) {
1596  rpl_move_parent(previous_dag, dag, p);
1597  }
1598  }
1599  } else {
1600  if(p->rank == dio->rank) {
1601  PRINTF("RPL: Received consistent DIO\n");
1602  if(dag->joined) {
1603  instance->dio_counter++;
1604  }
1605  }
1606  }
1607  p->rank = dio->rank;
1608 
1609  if(dio->rank == RPL_INFINITE_RANK && p == dag->preferred_parent) {
1610  /* Our preferred parent advertised an infinite rank, reset DIO timer */
1611  rpl_reset_dio_timer(instance);
1612  }
1613 
1614  /* Parent info has been updated, trigger rank recalculation */
1615  p->flags |= RPL_PARENT_FLAG_UPDATED;
1616 
1617  PRINTF("RPL: preferred DAG ");
1618  PRINT6ADDR(&instance->current_dag->dag_id);
1619  PRINTF(", rank %u, min_rank %u, ",
1620  instance->current_dag->rank, instance->current_dag->min_rank);
1621  PRINTF("parent rank %u, link metric %u\n",
1622  p->rank, rpl_get_parent_link_metric(p));
1623 
1624  /* We have allocated a candidate parent; process the DIO further. */
1625 
1626 #if RPL_WITH_MC
1627  memcpy(&p->mc, &dio->mc, sizeof(p->mc));
1628 #endif /* RPL_WITH_MC */
1629  if(rpl_process_parent_event(instance, p) == 0) {
1630  PRINTF("RPL: The candidate parent is rejected\n");
1631  return;
1632  }
1633 
1634  /* We don't use route control, so we can have only one official parent. */
1635  if(dag->joined && p == dag->preferred_parent) {
1636  if(should_refresh_routes(instance, dio, p)) {
1637  /* Our parent is requesting a new DAO. Increment DTSN in turn,
1638  * in both storing and non-storing mode (see RFC6550 section 9.6.) */
1639  RPL_LOLLIPOP_INCREMENT(instance->dtsn_out);
1640  rpl_schedule_dao(instance);
1641  }
1642  /* We received a new DIO from our preferred parent.
1643  * Call uip_ds6_defrt_add to set a fresh value for the lifetime counter */
1644  uip_ds6_defrt_add(from, RPL_DEFAULT_ROUTE_INFINITE_LIFETIME ? 0 : RPL_LIFETIME(instance, instance->default_lifetime));
1645  }
1646  p->dtsn = dio->dtsn;
1647 }
1648 /*---------------------------------------------------------------------------*/
1649 /** @} */
static uip_ipaddr_t ipaddr
Pointer to prefix information option in uip_buf.
Definition: uip-nd6.c:124
uip_lladdr_t uip_lladdr
Host L2 address.
Definition: uip6.c:107
void ctimer_stop(struct ctimer *c)
Stop a pending callback timer.
Definition: ctimer.c:149
RPL DAG structure.
Definition: rpl.h:135
static uip_ds6_nbr_t * nbr
Pointer to llao option in uip_buf.
Definition: uip-nd6.c:114
RPL instance structure.
Definition: rpl.h:219
#define ROOT_RANK
Rank of a root node.
Definition: rpl-types.h:78
static uip_ds6_addr_t * addr
Pointer to a nbr cache entry.
Definition: uip-nd6.c:115
void rpl_schedule_probing_now(void)
Schedule probing within a few seconds.
IPv6 Neighbor cache (link-layer/IPv6 address mapping)
A set of debugging macros for the IP stack
#define RPL_LIFETIME(lifetime)
Compute lifetime, accounting for the lifetime unit.
Definition: rpl-types.h:72
void uip_ds6_set_addr_iid(uip_ipaddr_t *ipaddr, uip_lladdr_t *lladdr)
set the last 64 bits of an IP address based on the MAC address
Definition: uip-ds6.c:557
RPL prefix information.
Definition: rpl.h:126
int rpl_dag_root_is_root(void)
Tells whether we are DAG root or not.
Definition: rpl-dag-root.c:142
API for RPL objective functions (OF)
Definition: rpl.h:201
This header file contains configuration directives for uIPv6 multicast support.
#define CLOCK_SECOND
A second, measured in system clock time.
Definition: clock.h:82
#define DAG_RANK(fixpt_rank)
Return DAG RANK as per RFC 6550 (rank divided by min_hoprankinc)
Definition: rpl-types.h:81
int rpl_has_downward_route(void)
Get the RPL&#39;s best guess on if we have downward route or not.
Definition: rpl-dag.c:1017
Header file for the callback timer
Linked list manipulation routines.
Unicast address structure.
Definition: uip-ds6.h:204
rpl_dag_t * rpl_get_any_dag(void)
Returns pointer to any DAG (for compatibility with legagy RPL code)
Definition: rpl-dag.c:1051
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
Memory block allocation routines.
uip_ds6_addr_t * uip_ds6_addr_add(uip_ipaddr_t *ipaddr, unsigned long vlifetime, uint8_t type)
Add a unicast address to the interface.
Definition: uip-ds6.c:341
uip_ds6_nbr_t * rpl_icmp6_update_nbr_table(uip_ipaddr_t *from, nbr_table_reason_t reason, void *data)
Updates IPv6 neighbor cache on incoming link-local RPL ICMPv6 messages.
Definition: rpl-icmp6.c:196
Header file for the uIP TCP/IP stack.
Header file for IPv6 Neighbor discovery (RFC 4861)
void rpl_process_dio(uip_ipaddr_t *from, rpl_dio_t *dio)
Processes incoming DIO.
Definition: rpl-dag.c:1455
int rpl_has_joined(void)
Tells whether the node has joined a network or not.
Definition: rpl-dag.c:1011
void rpl_local_repair(const char *str)
Triggers a RPL local repair.
Definition: rpl-dag.c:232
rpl_instance_t * rpl_get_default_instance(void)
Returns pointer to the default instance (for compatibility with legagy RPL code)
Definition: rpl-dag.c:624
void rpl_dag_init(void)
Initializes rpl-dag module.
Definition: rpl-dag.c:141
An entry in the nbr cache.
Definition: uip-ds6-nbr.h:69
void rpl_schedule_probing(void)
Schedule probing with delay RPL_PROBING_DELAY_FUNC()