Contiki-NG
rpl.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2009, 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  * \file
34  * ContikiRPL, an implementation of RPL: IPv6 Routing Protocol
35  * for Low-Power and Lossy Networks (IETF RFC 6550)
36  *
37  * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
38  */
39 
40 /**
41  * \addtogroup uip
42  * @{
43  */
44 
45 #include "net/ipv6/uip.h"
46 #include "net/ipv6/tcpip.h"
47 #include "net/ipv6/uip-ds6.h"
48 #include "net/ipv6/uip-sr.h"
49 #include "net/ipv6/uip-icmp6.h"
50 #include "net/routing/routing.h"
51 #include "net/routing/rpl-classic/rpl-private.h"
52 #include "net/routing/rpl-classic/rpl-dag-root.h"
54 
55 #include "sys/log.h"
56 
57 #include <limits.h>
58 #include <string.h>
59 
60 #define LOG_MODULE "RPL"
61 #define LOG_LEVEL LOG_LEVEL_RPL
62 
63 #if RPL_CONF_STATS
64 rpl_stats_t rpl_stats;
65 #endif
66 
67 static enum rpl_mode mode = RPL_MODE_MESH;
68 /*---------------------------------------------------------------------------*/
69 enum rpl_mode
71 {
72  return mode;
73 }
74 /*---------------------------------------------------------------------------*/
75 enum rpl_mode
76 rpl_set_mode(enum rpl_mode m)
77 {
78  enum rpl_mode oldmode = mode;
79 
80  /* We need to do different things depending on what mode we are
81  switching to. */
82  if(m == RPL_MODE_MESH) {
83 
84  /* If we switch to mesh mode, we should send out a DAO message to
85  inform our parent that we now are reachable. Before we do this,
86  we must set the mode variable, since DAOs will not be sent if
87  we are in feather mode. */
88  LOG_DBG("rpl_set_mode: switching to mesh mode\n");
89  mode = m;
90 
91  if(default_instance != NULL) {
92  rpl_schedule_dao_immediately(default_instance);
93  }
94  } else if(m == RPL_MODE_FEATHER) {
95 
96  LOG_INFO("rpl_set_mode: switching to feather mode\n");
97  if(default_instance != NULL) {
98  LOG_INFO("rpl_set_mode: RPL sending DAO with zero lifetime\n");
99  if(default_instance->current_dag != NULL) {
100  dao_output(default_instance->current_dag->preferred_parent, RPL_ZERO_LIFETIME);
101  }
102  rpl_cancel_dao(default_instance);
103  } else {
104  LOG_INFO("rpl_set_mode: no default instance\n");
105  }
106 
107  mode = m;
108  } else {
109  mode = m;
110  }
111 
112  return oldmode;
113 }
114 /*---------------------------------------------------------------------------*/
115 void
116 rpl_purge_routes(void)
117 {
118  uip_ds6_route_t *r;
119  uip_ipaddr_t prefix;
120  rpl_dag_t *dag;
121 #if RPL_WITH_MULTICAST
122  uip_mcast6_route_t *mcast_route;
123 #endif
124 
125  /* First pass, decrement lifetime */
126  r = uip_ds6_route_head();
127 
128  while(r != NULL) {
129  if(r->state.lifetime >= 1 && r->state.lifetime != RPL_ROUTE_INFINITE_LIFETIME) {
130  /*
131  * If a route is at lifetime == 1, set it to 0, scheduling it for
132  * immediate removal below. This achieves the same as the original code,
133  * which would delete lifetime <= 1
134  */
135  r->state.lifetime--;
136  }
137  r = uip_ds6_route_next(r);
138  }
139 
140  /* Second pass, remove dead routes */
141  r = uip_ds6_route_head();
142 
143  while(r != NULL) {
144  if(r->state.lifetime < 1) {
145  /* Routes with lifetime == 1 have only just been decremented from 2 to 1,
146  * thus we want to keep them. Hence < and not <= */
147  uip_ipaddr_copy(&prefix, &r->ipaddr);
148  uip_ds6_route_rm(r);
149  r = uip_ds6_route_head();
150  LOG_INFO("No more routes to ");
151  LOG_INFO_6ADDR(&prefix);
152  dag = default_instance->current_dag;
153  /* Propagate this information with a No-Path DAO to preferred parent if we are not a RPL Root */
154  if(dag->rank != ROOT_RANK(default_instance)) {
155  LOG_INFO_(" -> generate No-Path DAO\n");
156  dao_output_target(dag->preferred_parent, &prefix, RPL_ZERO_LIFETIME);
157  /* Don't schedule more than 1 No-Path DAO, let next iteration handle that */
158  return;
159  }
160  LOG_INFO_("\n");
161  } else {
162  r = uip_ds6_route_next(r);
163  }
164  }
165 
166 #if RPL_WITH_MULTICAST
167  mcast_route = uip_mcast6_route_list_head();
168 
169  while(mcast_route != NULL) {
170  if(mcast_route->lifetime <= 1) {
171  uip_mcast6_route_rm(mcast_route);
172  mcast_route = uip_mcast6_route_list_head();
173  } else {
174  mcast_route->lifetime--;
175  mcast_route = list_item_next(mcast_route);
176  }
177  }
178 #endif
179 }
180 /*---------------------------------------------------------------------------*/
181 void
182 rpl_remove_routes(rpl_dag_t *dag)
183 {
184  uip_ds6_route_t *r;
185 #if RPL_WITH_MULTICAST
186  uip_mcast6_route_t *mcast_route;
187 #endif
188 
189  r = uip_ds6_route_head();
190 
191  while(r != NULL) {
192  if(r->state.dag == dag) {
193  uip_ds6_route_rm(r);
194  r = uip_ds6_route_head();
195  } else {
196  r = uip_ds6_route_next(r);
197  }
198  }
199 
200 #if RPL_WITH_MULTICAST
201  mcast_route = uip_mcast6_route_list_head();
202 
203  while(mcast_route != NULL) {
204  if(mcast_route->dag == dag) {
205  uip_mcast6_route_rm(mcast_route);
206  mcast_route = uip_mcast6_route_list_head();
207  } else {
208  mcast_route = list_item_next(mcast_route);
209  }
210  }
211 #endif
212 }
213 /*---------------------------------------------------------------------------*/
214 void
215 rpl_remove_routes_by_nexthop(uip_ipaddr_t *nexthop, rpl_dag_t *dag)
216 {
217  uip_ds6_route_t *r;
218 
219  r = uip_ds6_route_head();
220 
221  while(r != NULL) {
222  if(uip_ipaddr_cmp(uip_ds6_route_nexthop(r), nexthop) &&
223  r->state.dag == dag) {
224  r->state.lifetime = 0;
225  }
226  r = uip_ds6_route_next(r);
227  }
228  LOG_ANNOTATE("#L %u 0\n", nexthop->u8[sizeof(uip_ipaddr_t) - 1]);
229 }
230 /*---------------------------------------------------------------------------*/
232 rpl_add_route(rpl_dag_t *dag, uip_ipaddr_t *prefix, int prefix_len,
233  uip_ipaddr_t *next_hop)
234 {
235  uip_ds6_route_t *rep;
236 
237  if((rep = uip_ds6_route_add(prefix, prefix_len, next_hop)) == NULL) {
238  LOG_ERR("No space for more route entries\n");
239  return NULL;
240  }
241 
242  rep->state.dag = dag;
243  rep->state.lifetime = RPL_LIFETIME(dag->instance, dag->instance->default_lifetime);
244  /* always clear state flags for the no-path received when adding/refreshing */
245  RPL_ROUTE_CLEAR_NOPATH_RECEIVED(rep);
246 
247  LOG_INFO("Added a route to ");
248  LOG_INFO_6ADDR(prefix);
249  LOG_INFO_("/%d via ", prefix_len);
250  LOG_INFO_6ADDR(next_hop);
251  LOG_INFO_("\n");
252 
253  return rep;
254 }
255 /*---------------------------------------------------------------------------*/
256 void
257 rpl_link_callback(const linkaddr_t *addr, int status, int numtx)
258 {
259  uip_ipaddr_t ipaddr;
260  rpl_parent_t *parent;
261  rpl_instance_t *instance;
262  rpl_instance_t *end;
263 
264  uip_ip6addr(&ipaddr, 0xfe80, 0, 0, 0, 0, 0, 0, 0);
265  uip_ds6_set_addr_iid(&ipaddr, (uip_lladdr_t *)addr);
266 
267  for(instance = &instance_table[0], end = instance + RPL_MAX_INSTANCES; instance < end; ++instance) {
268  if(instance->used == 1 ) {
269  parent = rpl_find_parent_any_dag(instance, &ipaddr);
270  if(parent != NULL) {
271  /* If this is the neighbor we were probing urgently, mark urgent
272  probing as done */
273 #if RPL_WITH_PROBING
274  if(instance->urgent_probing_target == parent) {
275  instance->urgent_probing_target = NULL;
276  }
277 #endif /* RPL_WITH_PROBING */
278  /* Trigger DAG rank recalculation. */
279  LOG_DBG("rpl_link_callback triggering update\n");
280  parent->flags |= RPL_PARENT_FLAG_UPDATED;
281  }
282  }
283  }
284 }
285 /*---------------------------------------------------------------------------*/
286 void
287 rpl_ipv6_neighbor_callback(uip_ds6_nbr_t *nbr)
288 {
289  rpl_parent_t *p;
290  rpl_instance_t *instance;
291  rpl_instance_t *end;
292 
293  LOG_DBG("Neighbor state changed for ");
294  LOG_DBG_6ADDR(&nbr->ipaddr);
295 #if UIP_ND6_SEND_NS || UIP_ND6_SEND_RA
296  LOG_DBG_(", nscount=%u, state=%u\n", nbr->nscount, nbr->state);
297 #else /* UIP_ND6_SEND_NS || UIP_ND6_SEND_RA */
298  LOG_DBG_(", state=%u\n", nbr->state);
299 #endif /* UIP_ND6_SEND_NS || UIP_ND6_SEND_RA */
300  for(instance = &instance_table[0], end = instance + RPL_MAX_INSTANCES; instance < end; ++instance) {
301  if(instance->used == 1 ) {
302  p = rpl_find_parent_any_dag(instance, &nbr->ipaddr);
303  if(p != NULL) {
304  p->rank = RPL_INFINITE_RANK;
305  /* Trigger DAG rank recalculation. */
306  LOG_DBG("rpl_ipv6_neighbor_callback infinite rank\n");
307  p->flags |= RPL_PARENT_FLAG_UPDATED;
308  }
309  }
310  }
311 }
312 /*---------------------------------------------------------------------------*/
313 void
314 rpl_purge_dags(void)
315 {
316  rpl_instance_t *instance;
317  rpl_instance_t *end;
318  int i;
319 
320  for(instance = &instance_table[0], end = instance + RPL_MAX_INSTANCES;
321  instance < end; ++instance) {
322  if(instance->used) {
323  for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; i++) {
324  if(instance->dag_table[i].used) {
325  if(instance->dag_table[i].lifetime == 0) {
326  if(!instance->dag_table[i].joined) {
327  LOG_INFO("Removing dag ");
328  LOG_INFO_6ADDR(&instance->dag_table[i].dag_id);
329  LOG_INFO_("\n");
330  rpl_free_dag(&instance->dag_table[i]);
331  }
332  } else {
333  instance->dag_table[i].lifetime--;
334  }
335  }
336  }
337  }
338  }
339 }
340 /*---------------------------------------------------------------------------*/
341 static void
342 init(void)
343 {
344  uip_ipaddr_t rplmaddr;
345  LOG_INFO("rpl-classic started\n");
346  default_instance = NULL;
347 
348  rpl_dag_init();
349  rpl_reset_periodic_timer();
350  rpl_icmp6_register_handlers();
351 
352  /* add rpl multicast address */
354  uip_ds6_maddr_add(&rplmaddr);
355 
356 #if RPL_CONF_STATS
357  memset(&rpl_stats, 0, sizeof(rpl_stats));
358 #endif
359 
360 #if RPL_WITH_NON_STORING
361  uip_sr_init();
362 #endif /* RPL_WITH_NON_STORING */
363 }
364 /*---------------------------------------------------------------------------*/
365 static int
366 get_sr_node_ipaddr(uip_ipaddr_t *addr, const uip_sr_node_t *node)
367 {
368  if(addr != NULL && node != NULL) {
369  memcpy(addr, &((rpl_dag_t *)node->graph)->dag_id, 8);
370  memcpy(((unsigned char *)addr) + 8, &node->link_identifier, 8);
371  return 1;
372  } else {
373  return 0;
374  }
375 }
376 /*---------------------------------------------------------------------------*/
377 static void
378 global_repair(const char *str)
379 {
380  rpl_dag_t *dag = rpl_get_any_dag();
381  if(dag != NULL && dag->instance != NULL) {
382  rpl_repair_root(dag->instance->instance_id);
383  }
384 }
385 /*---------------------------------------------------------------------------*/
386 static void
387 local_repair(const char *str)
388 {
389  rpl_dag_t *dag = rpl_get_any_dag();
390  if(dag != NULL) {
391  rpl_local_repair(dag->instance);
392  }
393 }
394 /*---------------------------------------------------------------------------*/
395 static void
396 drop_route(uip_ds6_route_t *route)
397 {
398  /* If we are the root of the network, trigger a global repair before
399  the route gets removed */
400  rpl_dag_t *dag;
401  dag = (rpl_dag_t *)route->state.dag;
402  if(dag != NULL && dag->instance != NULL) {
403  rpl_repair_root(dag->instance->instance_id);
404  }
405 }
406 /*---------------------------------------------------------------------------*/
407 static void
408 leave_network(void)
409 {
410  LOG_ERR("leave_network not supported in RPL Classic\n");
411 }
412 /*---------------------------------------------------------------------------*/
413 static int
414 get_root_ipaddr(uip_ipaddr_t *ipaddr)
415 {
416  rpl_dag_t *dag;
417  /* Use the DAG id as server address if no other has been specified */
418  dag = rpl_get_any_dag();
419  if(dag != NULL && ipaddr != NULL) {
420  uip_ipaddr_copy(ipaddr, &dag->dag_id);
421  return 1;
422  }
423  return 0;
424 }
425 /*---------------------------------------------------------------------------*/
426 uint8_t
428 {
429  /*
430  * Confusingly, most of the RPL code uses the `rpl_mode` variable
431  * ony to check whether the node is in mesh or feather mode,
432  * and makes decision about the leaf status based on the preprocessor flag.
433  * For consistency, do the same here.
434  */
435  return RPL_LEAF_ONLY ? 1 : 0;
436 }
437 /*---------------------------------------------------------------------------*/
438 const struct routing_driver rpl_classic_driver = {
439  "RPL Classic",
440  init,
450  local_repair,
457  rpl_ipv6_neighbor_callback,
458  drop_route,
460 };
461 /*---------------------------------------------------------------------------*/
462 
463 /** @}*/
static uip_ipaddr_t ipaddr
Pointer to prefix information option in uip_buf.
Definition: uip-nd6.c:116
#define uip_ip6addr(addr, addr0, addr1, addr2, addr3, addr4, addr5, addr6, addr7)
Construct an IPv6 address from eight 16-bit words.
Definition: uip.h:958
void rpl_link_callback(const linkaddr_t *addr, int status, int numtx)
Called by lower layers after every packet transmission.
Definition: rpl.c:257
Header for the Contiki/uIP interface.
Header file for ICMPv6 message and error handing (RFC 4443)
int rpl_dag_root_start(void)
Set the node as root and start a DAG.
Definition: rpl-dag-root.c:99
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
enum rpl_mode rpl_get_mode(void)
Get the RPL mode.
Definition: rpl.c:70
void(* drop_route)(uip_ds6_route_t *route)
Called by uIP if it has decided to drop a route because.
Definition: routing.h:184
int rpl_ext_header_srh_get_next_hop(uip_ipaddr_t *ipaddr)
Look for next hop from SRH of current uIP packet.
void uip_sr_init(void)
Initialize this module.
Definition: uip-sr.c:186
uint8_t rpl_is_in_leaf_mode(void)
Tells whether the protocol is in leaf mode.
Definition: rpl.c:427
#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
int rpl_ext_header_update(void)
Adds/updates all RPL extension headers to current uIP packet.
int rpl_dag_root_is_root(void)
Tells whether we are DAG root or not.
Definition: rpl-dag-root.c:153
int rpl_ext_header_hbh_update(uint8_t *ext_buf, int opt_offset)
Process and update the RPL hop-by-hop extension headers of the current uIP packet.
void(* global_repair)(const char *str)
Triggers a global topology repair.
Definition: routing.h:120
Source routing support.
Header file for IPv6-related data structures.
void(* init)(void)
Initialize the routing protocol.
Definition: routing.h:63
An entry in the routing table.
This header file contains configuration directives for uIPv6 multicast support.
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:1039
void rpl_dag_root_set_prefix(uip_ipaddr_t *prefix, uip_ipaddr_t *iid)
Set a prefix in case the node is later set as dag root.
Definition: rpl-dag-root.c:88
void * dag
Pointer to an rpl_dag_t struct.
Routing driver header file
rpl_dag_t * rpl_get_any_dag(void)
Returns pointer to any DAG (for compatibility with legagy RPL code)
Definition: rpl-dag.c:1073
#define uip_ipaddr_copy(dest, src)
Copy an IP address from one place to another.
Definition: uip.h:1015
uint32_t lifetime
Entry lifetime seconds.
An entry in the multicast routing table.
void(* leave_network)(void)
Leave the network the node is part of.
Definition: routing.h:102
void uip_mcast6_route_rm(uip_mcast6_route_t *route)
Remove a multicast route.
bool rpl_ext_header_remove(void)
Removes all RPL extension headers.
Header file for the uIP TCP/IP stack.
void(* local_repair)(const char *str)
Triggers a RPL local topology repair.
Definition: routing.h:126
int(* get_sr_node_ipaddr)(uip_ipaddr_t *addr, const uip_sr_node_t *node)
Returns the global IPv6 address of a source routing node.
Definition: routing.h:97
int(* get_root_ipaddr)(uip_ipaddr_t *ipaddr)
Returns the IPv6 address of the network root, if any.
Definition: routing.h:89
#define uip_create_linklocal_rplnodes_mcast(addr)
Set IP address addr to the link-local, all-rpl-nodes multicast address.
Definition: rpl-types.h:54
void rpl_local_repair(const char *str)
Triggers a RPL local repair.
Definition: rpl-dag.c:240
Header file for the logging system
int rpl_has_joined(void)
Tells whether the node has joined a network or not.
Definition: rpl.c:120
The structure of a routing protocol driver.
Definition: routing.h:60
void * list_item_next(void *item)
Get the next item following this item.
Definition: list.c:322
A node in a source routing graph, stored at the root and representing all child-parent relationship...
Definition: uip-sr.h:92
uip_mcast6_route_t * uip_mcast6_route_list_head(void)
Retrieve a pointer to the start of the multicast routes list.
enum rpl_mode rpl_set_mode(enum rpl_mode m)
Set the RPL mode.
Definition: rpl.c:76
void rpl_dag_init(void)
Initializes rpl-dag module.
Definition: rpl-dag.c:143
int rpl_ext_header_srh_update(void)
Process and update SRH in-place, i.e.
The default nbr_table entry (when UIP_DS6_NBR_MULTI_IPV6_ADDRS is disabled), that implements nbr cach...
Definition: uip-ds6-nbr.h:105