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