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