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