Contiki-NG
uip-sr.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016, Inria.
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  * \addtogroup uip
34  * @{
35  *
36  * \file
37  * Source routing support
38  *
39  * \author Simon Duquennoy <simon.duquennoy@inria.fr>
40  */
41 
42 #include "contiki.h"
43 #include "net/ipv6/uip-sr.h"
44 #include "net/ipv6/uiplib.h"
45 #include "net/routing/routing.h"
46 #include "lib/list.h"
47 #include "lib/memb.h"
48 
49 /* Log configuration */
50 #include "sys/log.h"
51 #define LOG_MODULE "IPv6 SR"
52 #define LOG_LEVEL LOG_LEVEL_IPV6
53 
54 /* Total number of nodes */
55 static int num_nodes;
56 
57 /* Every known node in the network */
58 LIST(nodelist);
59 MEMB(nodememb, uip_sr_node_t, UIP_SR_LINK_NUM);
60 
61 /*---------------------------------------------------------------------------*/
62 int
64 {
65  return num_nodes;
66 }
67 /*---------------------------------------------------------------------------*/
68 static int
69 node_matches_address(void *graph, const uip_sr_node_t *node, const uip_ipaddr_t *addr)
70 {
71  if(node == NULL || addr == NULL || graph != node->graph) {
72  return 0;
73  } else {
74  uip_ipaddr_t node_ipaddr;
75  NETSTACK_ROUTING.get_sr_node_ipaddr(&node_ipaddr, node);
76  return uip_ipaddr_cmp(&node_ipaddr, addr);
77  }
78 }
79 /*---------------------------------------------------------------------------*/
81 uip_sr_get_node(void *graph, const uip_ipaddr_t *addr)
82 {
83  uip_sr_node_t *l;
84  for(l = list_head(nodelist); l != NULL; l = list_item_next(l)) {
85  /* Compare prefix and node identifier */
86  if(node_matches_address(graph, l, addr)) {
87  return l;
88  }
89  }
90  return NULL;
91 }
92 /*---------------------------------------------------------------------------*/
93 int
94 uip_sr_is_addr_reachable(void *graph, const uip_ipaddr_t *addr)
95 {
96  int max_depth = UIP_SR_LINK_NUM;
97  uip_ipaddr_t root_ipaddr;
98  uip_sr_node_t *node;
99  uip_sr_node_t *root_node;
100 
101  NETSTACK_ROUTING.get_root_ipaddr(&root_ipaddr);
102  node = uip_sr_get_node(graph, addr);
103  root_node = uip_sr_get_node(graph, &root_ipaddr);
104 
105  while(node != NULL && node != root_node && max_depth > 0) {
106  node = node->parent;
107  max_depth--;
108  }
109  return node != NULL && node == root_node;
110 }
111 /*---------------------------------------------------------------------------*/
112 void
113 uip_sr_expire_parent(void *graph, const uip_ipaddr_t *child, const uip_ipaddr_t *parent)
114 {
115  uip_sr_node_t *l = uip_sr_get_node(graph, child);
116  /* Check if parent matches */
117  if(l != NULL && node_matches_address(graph, l->parent, parent)) {
118  l->lifetime = UIP_SR_REMOVAL_DELAY;
119  }
120 }
121 /*---------------------------------------------------------------------------*/
123 uip_sr_update_node(void *graph, const uip_ipaddr_t *child, const uip_ipaddr_t *parent, uint32_t lifetime)
124 {
125  uip_sr_node_t *child_node = uip_sr_get_node(graph, child);
126  uip_sr_node_t *parent_node = uip_sr_get_node(graph, parent);
127  uip_sr_node_t *old_parent_node;
128 
129  if(parent != NULL) {
130  /* No node for the parent, add one with infinite lifetime */
131  if(parent_node == NULL) {
132  parent_node = uip_sr_update_node(graph, parent, NULL, UIP_SR_INFINITE_LIFETIME);
133  if(parent_node == NULL) {
134  LOG_ERR("NS: no space left for root node!\n");
135  return NULL;
136  }
137  }
138  }
139 
140  /* No node for this child, add one */
141  if(child_node == NULL) {
142  child_node = memb_alloc(&nodememb);
143  /* No space left, abort */
144  if(child_node == NULL) {
145  LOG_ERR("NS: no space left for child ");
146  LOG_ERR_6ADDR(child);
147  LOG_ERR_("\n");
148  return NULL;
149  }
150  child_node->parent = NULL;
151  list_add(nodelist, child_node);
152  num_nodes++;
153  }
154 
155  /* Initialize node */
156  child_node->graph = graph;
157  child_node->lifetime = lifetime;
158  memcpy(child_node->link_identifier, ((const unsigned char *)child) + 8, 8);
159 
160  /* Is the node reachable before the update? */
161  if(uip_sr_is_addr_reachable(graph, child)) {
162  old_parent_node = child_node->parent;
163  /* Update node */
164  child_node->parent = parent_node;
165  /* Has the node become unreachable? May happen if we create a loop. */
166  if(!uip_sr_is_addr_reachable(graph, child)) {
167  /* The new parent makes the node unreachable, restore old parent.
168  * We will take the update next time, with chances we know more of
169  * the topology and the loop is gone. */
170  child_node->parent = old_parent_node;
171  }
172  } else {
173  child_node->parent = parent_node;
174  }
175 
176  LOG_INFO("NS: updating link, child ");
177  LOG_INFO_6ADDR(child);
178  LOG_INFO_(", parent ");
179  LOG_INFO_6ADDR(parent);
180  LOG_INFO_(", lifetime %u, num_nodes %u\n", (unsigned)lifetime, num_nodes);
181 
182  return child_node;
183 }
184 /*---------------------------------------------------------------------------*/
185 void
187 {
188  num_nodes = 0;
189  memb_init(&nodememb);
190  list_init(nodelist);
191 }
192 /*---------------------------------------------------------------------------*/
195 {
196  return list_head(nodelist);
197 }
198 /*---------------------------------------------------------------------------*/
201 {
202  return list_item_next(item);
203 }
204 /*---------------------------------------------------------------------------*/
205 void
206 uip_sr_periodic(unsigned seconds)
207 {
208  uip_sr_node_t *l;
209  uip_sr_node_t *next;
210 
211  /* First pass, for all expired nodes, deallocate them iff no child points to them */
212  for(l = list_head(nodelist); l != NULL; l = next) {
213  next = list_item_next(l);
214  if(l->lifetime == 0) {
215  uip_sr_node_t *l2;
216  for(l2 = list_head(nodelist); l2 != NULL; l2 = list_item_next(l2)) {
217  if(l2->parent == l) {
218  break;
219  }
220  }
221  if(LOG_INFO_ENABLED) {
222  uip_ipaddr_t node_addr;
223  NETSTACK_ROUTING.get_sr_node_ipaddr(&node_addr, l);
224  LOG_INFO("NS: removing expired node ");
225  LOG_INFO_6ADDR(&node_addr);
226  LOG_INFO_("\n");
227  }
228  /* No child found, deallocate node */
229  list_remove(nodelist, l);
230  memb_free(&nodememb, l);
231  num_nodes--;
232  } else if(l->lifetime != UIP_SR_INFINITE_LIFETIME) {
233  l->lifetime = l->lifetime > seconds ? l->lifetime - seconds : 0;
234  }
235  }
236 }
237 /*---------------------------------------------------------------------------*/
238 void
240 {
241  uip_sr_node_t *l;
242  uip_sr_node_t *next;
243  for(l = list_head(nodelist); l != NULL; l = next) {
244  next = list_item_next(l);
245  list_remove(nodelist, l);
246  memb_free(&nodememb, l);
247  num_nodes--;
248  }
249 }
250 /*---------------------------------------------------------------------------*/
251 int
252 uip_sr_link_snprint(char *buf, int buflen, uip_sr_node_t *link)
253 {
254  int index = 0;
255  uip_ipaddr_t child_ipaddr;
256  uip_ipaddr_t parent_ipaddr;
257 
258  NETSTACK_ROUTING.get_sr_node_ipaddr(&child_ipaddr, link);
259  NETSTACK_ROUTING.get_sr_node_ipaddr(&parent_ipaddr, link->parent);
260 
261  if(LOG_WITH_COMPACT_ADDR) {
262  index += log_6addr_compact_snprint(buf+index, buflen-index, &child_ipaddr);
263  } else {
264  index += uiplib_ipaddr_snprint(buf+index, buflen-index, &child_ipaddr);
265  }
266  if(index >= buflen) {
267  return index;
268  }
269 
270  if(link->parent == NULL) {
271  index += snprintf(buf+index, buflen-index, " (DODAG root)");
272  if(index >= buflen) {
273  return index;
274  }
275  } else {
276  index += snprintf(buf+index, buflen-index, " to ");
277  if(index >= buflen) {
278  return index;
279  }
280  if(LOG_WITH_COMPACT_ADDR) {
281  index += log_6addr_compact_snprint(buf+index, buflen-index, &parent_ipaddr);
282  } else {
283  index += uiplib_ipaddr_snprint(buf+index, buflen-index, &parent_ipaddr);
284  }
285  if(index >= buflen) {
286  return index;
287  }
288  }
289  if(link->lifetime != UIP_SR_INFINITE_LIFETIME) {
290  index += snprintf(buf+index, buflen-index,
291  " (lifetime: %lu seconds)", (unsigned long)link->lifetime);
292  if(index >= buflen) {
293  return index;
294  }
295  } else {
296  index += snprintf(buf+index, buflen-index, " (lifetime: infinite)");
297  if(index >= buflen) {
298  return index;
299  }
300  }
301  return index;
302 }
303 /** @} */
int uip_sr_num_nodes(void)
Tells how many nodes are currently stored in the graph.
Definition: uip-sr.c:63
static uip_ds6_addr_t * addr
Pointer to a nbr cache entry.
Definition: uip-nd6.c:116
void uip_sr_free_all(void)
Deallocate all neighbors.
Definition: uip-sr.c:239
void uip_sr_init(void)
Initialize this module.
Definition: uip-sr.c:186
void uip_sr_expire_parent(void *graph, const uip_ipaddr_t *child, const uip_ipaddr_t *parent)
Expires a given child-parent link.
Definition: uip-sr.c:113
Source routing support.
uip_sr_node_t * uip_sr_node_next(uip_sr_node_t *item)
Returns the next element of the non-storing node list.
Definition: uip-sr.c:200
Header file for the IP address manipulation library.
void uip_sr_periodic(unsigned seconds)
A function called periodically.
Definition: uip-sr.c:206
Linked list manipulation routines.
void * list_head(list_t list)
Get a pointer to the first element of a list.
Definition: list.c:82
uip_sr_node_t * uip_sr_node_head(void)
Returns the head of the non-storing node list.
Definition: uip-sr.c:194
Routing driver header file
uip_sr_node_t * uip_sr_get_node(void *graph, const uip_ipaddr_t *addr)
Looks up for a source routing node from its IPv6 global address.
Definition: uip-sr.c:81
Memory block allocation routines.
void list_add(list_t list, void *item)
Add an item at the end of a list.
Definition: list.c:142
void list_init(list_t list)
Initialize a list.
Definition: list.c:65
int uip_sr_link_snprint(char *buf, int buflen, uip_sr_node_t *link)
Print a textual description of a source routing link.
Definition: uip-sr.c:252
#define LIST(name)
Declare a linked list.
Definition: list.h:88
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
Definition: memb.c:59
uip_sr_node_t * uip_sr_update_node(void *graph, const uip_ipaddr_t *child, const uip_ipaddr_t *parent, uint32_t lifetime)
Updates a child-parent link.
Definition: uip-sr.c:123
int log_6addr_compact_snprint(char *buf, size_t size, const uip_ipaddr_t *ipaddr)
Write at most size - 1 characters of the IP address to the output string, in a compact representation...
Definition: log.c:95
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
void memb_init(struct memb *m)
Initialize a memory block that was declared with MEMB().
Definition: memb.c:52
char memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
Definition: memb.c:79
Header file for the logging system
int uip_sr_is_addr_reachable(void *graph, const uip_ipaddr_t *addr)
Telle whether an address is reachable, i.e.
Definition: uip-sr.c:94
void list_remove(list_t list, void *item)
Remove a specific element from a list.
Definition: list.c:237
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
#define MEMB(name, structure, num)
Declare a memory block.
Definition: memb.h:89
int uiplib_ipaddr_snprint(char *buf, size_t size, const uip_ipaddr_t *addr)
Write at most size - 1 characters of the IP address to the output string.
Definition: uiplib.c:168