Contiki 2.6
|
00001 /** 00002 * \addtogroup uip6 00003 * @{ 00004 */ 00005 /* 00006 * Copyright (c) 2010, Swedish Institute of Computer Science. 00007 * All rights reserved. 00008 * 00009 * Redistribution and use in source and binary forms, with or without 00010 * modification, are permitted provided that the following conditions 00011 * are met: 00012 * 1. Redistributions of source code must retain the above copyright 00013 * notice, this list of conditions and the following disclaimer. 00014 * 2. Redistributions in binary form must reproduce the above copyright 00015 * notice, this list of conditions and the following disclaimer in the 00016 * documentation and/or other materials provided with the distribution. 00017 * 3. Neither the name of the Institute nor the names of its contributors 00018 * may be used to endorse or promote products derived from this software 00019 * without specific prior written permission. 00020 * 00021 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 00022 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00023 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00024 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 00025 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00026 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00027 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00028 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00029 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00030 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00031 * SUCH DAMAGE. 00032 * 00033 * This file is part of the Contiki operating system. 00034 * 00035 */ 00036 /** 00037 * \file 00038 * Logic for Directed Acyclic Graphs in RPL. 00039 * 00040 * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se> 00041 */ 00042 00043 00044 #include "contiki.h" 00045 #include "net/rpl/rpl-private.h" 00046 #include "net/uip.h" 00047 #include "net/uip-nd6.h" 00048 #include "lib/list.h" 00049 #include "lib/memb.h" 00050 #include "sys/ctimer.h" 00051 00052 #include <limits.h> 00053 #include <string.h> 00054 00055 #define DEBUG DEBUG_NONE 00056 #include "net/uip-debug.h" 00057 00058 #include "net/neighbor-info.h" 00059 00060 /************************************************************************/ 00061 extern rpl_of_t RPL_OF; 00062 static rpl_of_t * const objective_functions[] = {&RPL_OF}; 00063 00064 /************************************************************************/ 00065 #ifndef RPL_CONF_MAX_PARENTS_PER_DAG 00066 #define RPL_MAX_PARENTS_PER_DAG 8 00067 #else 00068 #define RPL_MAX_PARENTS_PER_DAG RPL_CONF_MAX_PARENTS_PER_DAG 00069 #endif /* !RPL_CONF_MAX_PARENTS_PER_DAG */ 00070 00071 /************************************************************************/ 00072 /* RPL definitions. */ 00073 00074 #ifndef RPL_CONF_GROUNDED 00075 #define RPL_GROUNDED 0 00076 #else 00077 #define RPL_GROUNDED RPL_CONF_GROUNDED 00078 #endif /* !RPL_CONF_GROUNDED */ 00079 00080 /************************************************************************/ 00081 /* Allocate parents from the same static MEMB chunk to reduce memory waste. */ 00082 MEMB(parent_memb, struct rpl_parent, 00083 RPL_MAX_PARENTS_PER_DAG * RPL_MAX_INSTANCES * RPL_MAX_DAG_PER_INSTANCE); 00084 /************************************************************************/ 00085 /* Allocate instance table. */ 00086 rpl_instance_t instance_table[RPL_MAX_INSTANCES]; 00087 rpl_instance_t *default_instance; 00088 /************************************************************************/ 00089 /* Greater-than function for the lollipop counter. */ 00090 /************************************************************************/ 00091 static int 00092 lollipop_greater_than(int a, int b) 00093 { 00094 /* Check if we are comparing an initial value with an old value */ 00095 if(a > RPL_LOLLIPOP_CIRCULAR_REGION && b <= RPL_LOLLIPOP_CIRCULAR_REGION) { 00096 return (RPL_LOLLIPOP_MAX_VALUE + 1 + b - a) > RPL_LOLLIPOP_SEQUENCE_WINDOWS; 00097 } 00098 /* Otherwise check if a > b and comparable => ok, or 00099 if they have wrapped and are still comparable */ 00100 return (a > b && (a - b) < RPL_LOLLIPOP_SEQUENCE_WINDOWS) || 00101 (a < b && (b - a) > (RPL_LOLLIPOP_CIRCULAR_REGION + 1- 00102 RPL_LOLLIPOP_SEQUENCE_WINDOWS)); 00103 } 00104 /************************************************************************/ 00105 /* Remove DAG parents with a rank that is at least the same as minimum_rank. */ 00106 static void 00107 remove_parents(rpl_dag_t *dag, rpl_rank_t minimum_rank) 00108 { 00109 rpl_parent_t *p, *p2; 00110 00111 PRINTF("RPL: Removing parents (minimum rank %u)\n", 00112 minimum_rank); 00113 00114 for(p = list_head(dag->parents); p != NULL; p = p2) { 00115 p2 = p->next; 00116 if(p->rank >= minimum_rank) { 00117 rpl_remove_parent(dag, p); 00118 } 00119 } 00120 } 00121 /************************************************************************/ 00122 static void 00123 nullify_parents(rpl_dag_t *dag, rpl_rank_t minimum_rank) 00124 { 00125 rpl_parent_t *p, *p2; 00126 00127 PRINTF("RPL: Removing parents (minimum rank %u)\n", 00128 minimum_rank); 00129 00130 for(p = list_head(dag->parents); p != NULL; p = p2) { 00131 p2 = p->next; 00132 if(p->rank >= minimum_rank) { 00133 rpl_nullify_parent(dag, p); 00134 } 00135 } 00136 } 00137 /************************************************************************/ 00138 static void 00139 remove_worst_parent(rpl_dag_t *dag, rpl_rank_t min_worst_rank) 00140 { 00141 rpl_parent_t *p, *worst; 00142 00143 PRINTF("RPL: Removing the worst parent\n"); 00144 00145 /* Find the parent with the highest rank. */ 00146 worst = NULL; 00147 for(p = list_head(dag->parents); p != NULL; p = list_item_next(p)) { 00148 if(p != dag->preferred_parent && 00149 (worst == NULL || p->rank > worst->rank)) { 00150 worst = p; 00151 } 00152 } 00153 /* Remove the neighbor if its rank is worse than the minimum worst rank. */ 00154 if(worst != NULL && worst->rank > min_worst_rank) { 00155 rpl_remove_parent(dag, worst); 00156 } 00157 } 00158 /************************************************************************/ 00159 static int 00160 should_send_dao(rpl_instance_t *instance, rpl_dio_t *dio, rpl_parent_t *p) 00161 { 00162 /* if MOP is set to no downward routes no DAO should be sent */ 00163 if(instance->mop == RPL_MOP_NO_DOWNWARD_ROUTES) { 00164 return 0; 00165 } 00166 /* check if the new DTSN is more recent */ 00167 return p == instance->current_dag->preferred_parent && 00168 (lollipop_greater_than(dio->dtsn, p->dtsn)); 00169 } 00170 /************************************************************************/ 00171 static int 00172 acceptable_rank(rpl_dag_t *dag, rpl_rank_t rank) 00173 { 00174 return rank != INFINITE_RANK && 00175 ((dag->instance->max_rankinc == 0) || 00176 DAG_RANK(rank, dag->instance) <= DAG_RANK(dag->min_rank + dag->instance->max_rankinc, dag->instance)); 00177 } 00178 /************************************************************************/ 00179 static rpl_dag_t * 00180 get_dag(uint8_t instance_id, uip_ipaddr_t *dag_id) 00181 { 00182 rpl_instance_t *instance; 00183 rpl_dag_t *dag; 00184 int i; 00185 00186 instance = rpl_get_instance(instance_id); 00187 if(instance == NULL) { 00188 return NULL; 00189 } 00190 00191 for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; ++i) { 00192 dag = &instance->dag_table[i]; 00193 if(dag->used && uip_ipaddr_cmp(&dag->dag_id, dag_id)) { 00194 return dag; 00195 } 00196 } 00197 00198 return NULL; 00199 } 00200 /************************************************************************/ 00201 rpl_dag_t * 00202 rpl_set_root(uint8_t instance_id, uip_ipaddr_t *dag_id) 00203 { 00204 rpl_dag_t *dag; 00205 rpl_instance_t *instance; 00206 uint8_t version; 00207 00208 version = RPL_LOLLIPOP_INIT; 00209 dag = get_dag(instance_id, dag_id); 00210 if(dag != NULL) { 00211 version = dag->version; 00212 RPL_LOLLIPOP_INCREMENT(version); 00213 PRINTF("RPL: Dropping a joined DAG when setting this node as root"); 00214 if(dag == dag->instance->current_dag) { 00215 dag->instance->current_dag = NULL; 00216 } 00217 rpl_free_dag(dag); 00218 } 00219 00220 dag = rpl_alloc_dag(instance_id, dag_id); 00221 if(dag == NULL) { 00222 PRINTF("RPL: Failed to allocate a DAG\n"); 00223 return NULL; 00224 } 00225 00226 instance = dag->instance; 00227 00228 dag->version = version; 00229 dag->joined = 1; 00230 dag->grounded = RPL_GROUNDED; 00231 instance->mop = RPL_MOP_DEFAULT; 00232 instance->of = &RPL_OF; 00233 dag->preferred_parent = NULL; 00234 00235 memcpy(&dag->dag_id, dag_id, sizeof(dag->dag_id)); 00236 00237 instance->dio_intdoubl = RPL_DIO_INTERVAL_DOUBLINGS; 00238 instance->dio_intmin = RPL_DIO_INTERVAL_MIN; 00239 /* The current interval must differ from the minimum interval in order to 00240 trigger a DIO timer reset. */ 00241 instance->dio_intcurrent = RPL_DIO_INTERVAL_MIN + 00242 RPL_DIO_INTERVAL_DOUBLINGS; 00243 instance->dio_redundancy = RPL_DIO_REDUNDANCY; 00244 instance->max_rankinc = RPL_MAX_RANKINC; 00245 instance->min_hoprankinc = RPL_MIN_HOPRANKINC; 00246 instance->default_lifetime = RPL_DEFAULT_LIFETIME; 00247 instance->lifetime_unit = RPL_DEFAULT_LIFETIME_UNIT; 00248 00249 dag->rank = ROOT_RANK(instance); 00250 00251 if(instance->current_dag != dag && instance->current_dag != NULL) { 00252 /* Remove routes installed by DAOs. */ 00253 rpl_remove_routes(instance->current_dag); 00254 00255 instance->current_dag->joined = 0; 00256 } 00257 00258 instance->current_dag = dag; 00259 instance->dtsn_out = RPL_LOLLIPOP_INIT; 00260 instance->of->update_metric_container(instance); 00261 default_instance = instance; 00262 00263 PRINTF("RPL: Node set to be a DAG root with DAG ID "); 00264 PRINT6ADDR(&dag->dag_id); 00265 PRINTF("\n"); 00266 00267 ANNOTATE("#A root=%u\n", dag->dag_id.u8[sizeof(dag->dag_id) - 1]); 00268 00269 rpl_reset_dio_timer(instance); 00270 00271 return dag; 00272 } 00273 /************************************************************************/ 00274 int 00275 rpl_repair_root(uint8_t instance_id) 00276 { 00277 rpl_instance_t *instance; 00278 00279 instance = rpl_get_instance(instance_id); 00280 if(instance == NULL || 00281 instance->current_dag->rank != ROOT_RANK(instance)) { 00282 return 0; 00283 } 00284 00285 RPL_LOLLIPOP_INCREMENT(instance->current_dag->version); 00286 RPL_LOLLIPOP_INCREMENT(instance->dtsn_out); 00287 rpl_reset_dio_timer(instance); 00288 return 1; 00289 } 00290 /************************************************************************/ 00291 static void 00292 set_ip_from_prefix(uip_ipaddr_t *ipaddr, rpl_prefix_t *prefix) 00293 { 00294 memset(ipaddr, 0, sizeof(uip_ipaddr_t)); 00295 memcpy(ipaddr, &prefix->prefix, (prefix->length + 7) / 8); 00296 uip_ds6_set_addr_iid(ipaddr, &uip_lladdr); 00297 } 00298 /************************************************************************/ 00299 static void 00300 check_prefix(rpl_prefix_t *last_prefix, rpl_prefix_t *new_prefix) 00301 { 00302 uip_ipaddr_t ipaddr; 00303 uip_ds6_addr_t *rep; 00304 00305 if(last_prefix != NULL && new_prefix != NULL && 00306 last_prefix->length == new_prefix->length && 00307 uip_ipaddr_prefixcmp(&last_prefix->prefix, &new_prefix->prefix, new_prefix->length) && 00308 last_prefix->flags == new_prefix->flags) { 00309 /* Nothing has changed. */ 00310 return; 00311 } 00312 00313 if(last_prefix != NULL) { 00314 set_ip_from_prefix(&ipaddr, last_prefix); 00315 rep = uip_ds6_addr_lookup(&ipaddr); 00316 if(rep != NULL) { 00317 PRINTF("RPL: removing global IP address "); 00318 PRINT6ADDR(&ipaddr); 00319 PRINTF("\n"); 00320 uip_ds6_addr_rm(rep); 00321 } 00322 } 00323 00324 if(new_prefix != NULL) { 00325 set_ip_from_prefix(&ipaddr, new_prefix); 00326 if(uip_ds6_addr_lookup(&ipaddr) == NULL) { 00327 PRINTF("RPL: adding global IP address "); 00328 PRINT6ADDR(&ipaddr); 00329 PRINTF("\n"); 00330 uip_ds6_addr_add(&ipaddr, 0, ADDR_AUTOCONF); 00331 } 00332 } 00333 } 00334 /************************************************************************/ 00335 int 00336 rpl_set_prefix(rpl_dag_t *dag, uip_ipaddr_t *prefix, unsigned len) 00337 { 00338 if(len > 128) { 00339 return 0; 00340 } 00341 00342 memset(&dag->prefix_info.prefix, 0, sizeof(dag->prefix_info.prefix)); 00343 memcpy(&dag->prefix_info.prefix, prefix, (len + 7) / 8); 00344 dag->prefix_info.length = len; 00345 dag->prefix_info.flags = UIP_ND6_RA_FLAG_AUTONOMOUS; 00346 PRINTF("RPL: Prefix set - will announce this in DIOs\n"); 00347 /* Autoconfigure an address if this node does not already have an address 00348 with this prefix. */ 00349 check_prefix(NULL, &dag->prefix_info); 00350 return 1; 00351 } 00352 /************************************************************************/ 00353 int 00354 rpl_set_default_route(rpl_instance_t *instance, uip_ipaddr_t *from) 00355 { 00356 if(instance->def_route != NULL) { 00357 if(instance->def_route->isused) { 00358 PRINTF("RPL: Removing default route through "); 00359 PRINT6ADDR(&instance->def_route->ipaddr); 00360 PRINTF("\n"); 00361 uip_ds6_defrt_rm(instance->def_route); 00362 } 00363 instance->def_route = NULL; 00364 } 00365 00366 if(from != NULL) { 00367 PRINTF("RPL: Adding default route through "); 00368 PRINT6ADDR(from); 00369 PRINTF("\n"); 00370 instance->def_route = uip_ds6_defrt_add(from, 00371 RPL_LIFETIME(instance, 00372 instance->default_lifetime)); 00373 if(instance->def_route == NULL) { 00374 return 0; 00375 } 00376 } 00377 return 1; 00378 } 00379 /************************************************************************/ 00380 rpl_instance_t * 00381 rpl_alloc_instance(uint8_t instance_id) 00382 { 00383 rpl_instance_t *instance, *end; 00384 00385 for(instance = &instance_table[0], end = instance + RPL_MAX_INSTANCES; instance < end; ++instance) { 00386 if(instance->used == 0) { 00387 memset(instance, 0, sizeof(*instance)); 00388 instance->instance_id = instance_id; 00389 instance->def_route = NULL; 00390 instance->used = 1; 00391 return instance; 00392 } 00393 } 00394 return NULL; 00395 } 00396 /************************************************************************/ 00397 rpl_dag_t * 00398 rpl_alloc_dag(uint8_t instance_id, uip_ipaddr_t *dag_id) 00399 { 00400 rpl_dag_t *dag, *end; 00401 rpl_instance_t *instance; 00402 00403 instance = rpl_get_instance(instance_id); 00404 if(instance == NULL) { 00405 instance = rpl_alloc_instance(instance_id); 00406 if(instance == NULL) { 00407 RPL_STAT(rpl_stats.mem_overflows++); 00408 return NULL; 00409 } 00410 } 00411 00412 for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) { 00413 if(!dag->used) { 00414 memset(dag, 0, sizeof(*dag)); 00415 LIST_STRUCT_INIT(dag, parents); 00416 dag->used = 1; 00417 dag->rank = INFINITE_RANK; 00418 dag->min_rank = INFINITE_RANK; 00419 dag->instance = instance; 00420 return dag; 00421 } 00422 } 00423 00424 RPL_STAT(rpl_stats.mem_overflows++); 00425 rpl_free_instance(instance); 00426 return NULL; 00427 } 00428 /************************************************************************/ 00429 void 00430 rpl_set_default_instance(rpl_instance_t *instance) 00431 { 00432 default_instance = instance; 00433 } 00434 /************************************************************************/ 00435 void 00436 rpl_free_instance(rpl_instance_t *instance) 00437 { 00438 rpl_dag_t *dag; 00439 rpl_dag_t *end; 00440 00441 PRINTF("RPL: Leaving the instance %u\n", instance->instance_id); 00442 00443 /* Remove any DAG inside this instance */ 00444 for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) { 00445 if(dag->used) { 00446 rpl_free_dag(dag); 00447 } 00448 } 00449 00450 rpl_set_default_route(instance, NULL); 00451 00452 ctimer_stop(&instance->dio_timer); 00453 ctimer_stop(&instance->dao_timer); 00454 00455 if(default_instance == instance) { 00456 default_instance = NULL; 00457 } 00458 00459 instance->used = 0; 00460 } 00461 /************************************************************************/ 00462 void 00463 rpl_free_dag(rpl_dag_t *dag) 00464 { 00465 if(dag->joined) { 00466 PRINTF("RPL: Leaving the DAG "); 00467 PRINT6ADDR(&dag->dag_id); 00468 PRINTF("\n"); 00469 dag->joined = 0; 00470 00471 /* Remove routes installed by DAOs. */ 00472 rpl_remove_routes(dag); 00473 00474 /* Remove autoconfigured address */ 00475 if((dag->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS)) { 00476 check_prefix(&dag->prefix_info, NULL); 00477 } 00478 00479 remove_parents(dag, 0); 00480 } 00481 dag->used = 0; 00482 } 00483 /************************************************************************/ 00484 rpl_parent_t * 00485 rpl_add_parent(rpl_dag_t *dag, rpl_dio_t *dio, uip_ipaddr_t *addr) 00486 { 00487 rpl_parent_t *p; 00488 00489 if(RPL_PARENT_COUNT(dag) == RPL_MAX_PARENTS_PER_DAG) { 00490 return NULL; 00491 } 00492 00493 p = memb_alloc(&parent_memb); 00494 if(p == NULL) { 00495 RPL_STAT(rpl_stats.mem_overflows++); 00496 return NULL; 00497 } 00498 memcpy(&p->addr, addr, sizeof(p->addr)); 00499 p->dag = dag; 00500 p->rank = dio->rank; 00501 p->dtsn = dio->dtsn; 00502 p->link_metric = INITIAL_LINK_METRIC; 00503 memcpy(&p->mc, &dio->mc, sizeof(p->mc)); 00504 list_add(dag->parents, p); 00505 return p; 00506 } 00507 /************************************************************************/ 00508 rpl_parent_t * 00509 rpl_find_parent(rpl_dag_t *dag, uip_ipaddr_t *addr) 00510 { 00511 rpl_parent_t *p; 00512 00513 for(p = list_head(dag->parents); p != NULL; p = p->next) { 00514 if(uip_ipaddr_cmp(&p->addr, addr)) { 00515 return p; 00516 } 00517 } 00518 return NULL; 00519 } 00520 00521 /************************************************************************/ 00522 static rpl_dag_t * 00523 find_parent_dag(rpl_instance_t *instance, uip_ipaddr_t *addr) 00524 { 00525 rpl_parent_t *p; 00526 rpl_dag_t *dag, *end; 00527 00528 for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) { 00529 if(dag->used) { 00530 for(p = list_head(dag->parents); p != NULL; p = p->next) { 00531 if(uip_ipaddr_cmp(&p->addr, addr)) { 00532 return dag; 00533 } 00534 } 00535 } 00536 } 00537 return NULL; 00538 } 00539 /************************************************************************/ 00540 rpl_parent_t * 00541 rpl_find_parent_any_dag(rpl_instance_t *instance, uip_ipaddr_t *addr) 00542 { 00543 rpl_parent_t *p; 00544 rpl_dag_t *dag, *end; 00545 00546 for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) { 00547 if(dag->used) { 00548 for(p = list_head(dag->parents); p != NULL; p = p->next) { 00549 if(uip_ipaddr_cmp(&p->addr, addr)) { 00550 return p; 00551 } 00552 } 00553 } 00554 } 00555 return NULL; 00556 } 00557 /************************************************************************/ 00558 rpl_dag_t * 00559 rpl_select_dag(rpl_instance_t *instance, rpl_parent_t *p) 00560 { 00561 rpl_parent_t *last_parent; 00562 rpl_dag_t *dag, *end, *best_dag; 00563 rpl_rank_t old_rank; 00564 00565 old_rank = instance->current_dag->rank; 00566 last_parent = instance->current_dag->preferred_parent; 00567 00568 best_dag = instance->current_dag; 00569 if(best_dag->rank != ROOT_RANK(instance)) { 00570 if(rpl_select_parent(p->dag) != NULL) { 00571 if(p->dag != best_dag) { 00572 best_dag = instance->of->best_dag(best_dag, p->dag); 00573 } 00574 } else if(p->dag == best_dag) { 00575 best_dag = NULL; 00576 for(dag = &instance->dag_table[0], end = dag + RPL_MAX_DAG_PER_INSTANCE; dag < end; ++dag) { 00577 if(dag->used && dag->preferred_parent != NULL && dag->preferred_parent->rank != INFINITE_RANK) { 00578 if(best_dag == NULL) { 00579 best_dag = dag; 00580 } else { 00581 best_dag = instance->of->best_dag(best_dag, dag); 00582 } 00583 } 00584 } 00585 } 00586 } 00587 00588 if(best_dag == NULL) { 00589 /* No parent found: the calling function handle this problem. */ 00590 return NULL; 00591 } 00592 00593 if(instance->current_dag != best_dag) { 00594 /* Remove routes installed by DAOs. */ 00595 rpl_remove_routes(instance->current_dag); 00596 00597 PRINTF("RPL: New preferred DAG: "); 00598 PRINT6ADDR(&best_dag->dag_id); 00599 PRINTF("\n"); 00600 00601 if(best_dag->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) { 00602 check_prefix(&instance->current_dag->prefix_info, &best_dag->prefix_info); 00603 } else if(instance->current_dag->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) { 00604 check_prefix(&instance->current_dag->prefix_info, NULL); 00605 } 00606 00607 best_dag->joined = 1; 00608 instance->current_dag->joined = 0; 00609 instance->current_dag = best_dag; 00610 } 00611 00612 instance->of->update_metric_container(instance); 00613 /* Update the DAG rank. */ 00614 best_dag->rank = instance->of->calculate_rank(best_dag->preferred_parent, 0); 00615 if(best_dag->rank < best_dag->min_rank) { 00616 best_dag->min_rank = best_dag->rank; 00617 } else if(!acceptable_rank(best_dag, best_dag->rank)) { 00618 PRINTF("RPL: New rank unacceptable!\n"); 00619 instance->current_dag->preferred_parent = NULL; 00620 if(instance->mop != RPL_MOP_NO_DOWNWARD_ROUTES && last_parent != NULL) { 00621 /* Send a No-Path DAO to the removed preferred parent. */ 00622 dao_output(last_parent, RPL_ZERO_LIFETIME); 00623 } 00624 return NULL; 00625 } 00626 00627 if(best_dag->preferred_parent != last_parent) { 00628 rpl_set_default_route(instance, &best_dag->preferred_parent->addr); 00629 PRINTF("RPL: Changed preferred parent, rank changed from %u to %u\n", 00630 (unsigned)old_rank, best_dag->rank); 00631 RPL_STAT(rpl_stats.parent_switch++); 00632 if(instance->mop != RPL_MOP_NO_DOWNWARD_ROUTES) { 00633 if(last_parent != NULL) { 00634 /* Send a No-Path DAO to the removed preferred parent. */ 00635 dao_output(last_parent, RPL_ZERO_LIFETIME); 00636 } 00637 /* The DAO parent set changed - schedule a DAO transmission. */ 00638 RPL_LOLLIPOP_INCREMENT(instance->dtsn_out); 00639 rpl_schedule_dao(instance); 00640 } 00641 rpl_reset_dio_timer(instance); 00642 } else if(best_dag->rank != old_rank) { 00643 PRINTF("RPL: Preferred parent update, rank changed from %u to %u\n", 00644 (unsigned)old_rank, best_dag->rank); 00645 } 00646 return best_dag; 00647 } 00648 /************************************************************************/ 00649 rpl_parent_t * 00650 rpl_select_parent(rpl_dag_t *dag) 00651 { 00652 rpl_parent_t *p, *best; 00653 00654 best = NULL; 00655 for(p = list_head(dag->parents); p != NULL; p = p->next) { 00656 if(p->rank == INFINITE_RANK) { 00657 /* ignore this neighbor */ 00658 } else if(best == NULL) { 00659 best = p; 00660 } else { 00661 best = dag->instance->of->best_parent(best, p); 00662 } 00663 } 00664 00665 if(best != NULL) { 00666 dag->preferred_parent = best; 00667 } 00668 00669 return best; 00670 } 00671 /************************************************************************/ 00672 void 00673 rpl_remove_parent(rpl_dag_t *dag, rpl_parent_t *parent) 00674 { 00675 rpl_nullify_parent(dag, parent); 00676 00677 PRINTF("RPL: Removing parent "); 00678 PRINT6ADDR(&parent->addr); 00679 PRINTF("\n"); 00680 00681 list_remove(dag->parents, parent); 00682 memb_free(&parent_memb, parent); 00683 } 00684 /************************************************************************/ 00685 void 00686 rpl_nullify_parent(rpl_dag_t *dag, rpl_parent_t *parent) 00687 { 00688 if(parent == dag->preferred_parent) { 00689 dag->preferred_parent = NULL; 00690 dag->rank = INFINITE_RANK; 00691 if(dag->joined) { 00692 if(dag->instance->def_route != NULL) { 00693 if(dag->instance->def_route->isused) { 00694 PRINTF("RPL: Removing default route "); 00695 PRINT6ADDR(&parent->addr); 00696 PRINTF("\n"); 00697 uip_ds6_defrt_rm(dag->instance->def_route); 00698 } 00699 dag->instance->def_route = NULL; 00700 } 00701 dao_output(parent, RPL_ZERO_LIFETIME); 00702 } 00703 } 00704 00705 PRINTF("RPL: Nullifying parent "); 00706 PRINT6ADDR(&parent->addr); 00707 PRINTF("\n"); 00708 } 00709 /************************************************************************/ 00710 void 00711 rpl_move_parent(rpl_dag_t *dag_src, rpl_dag_t *dag_dst, rpl_parent_t *parent) 00712 { 00713 if(parent == dag_src->preferred_parent) { 00714 dag_src->preferred_parent = NULL; 00715 dag_src->rank = INFINITE_RANK; 00716 if(dag_src->joined && dag_src->instance->def_route != NULL) { 00717 if(dag_src->instance->def_route->isused) { 00718 PRINTF("RPL: Removing default route "); 00719 PRINT6ADDR(&parent->addr); 00720 PRINTF("\n"); 00721 uip_ds6_defrt_rm(dag_src->instance->def_route); 00722 } 00723 dag_src->instance->def_route = NULL; 00724 } 00725 } else if(dag_src->joined) { 00726 /* Remove uIPv6 routes that have this parent as the next hop. */ 00727 rpl_remove_routes_by_nexthop(&parent->addr, dag_src); 00728 } 00729 00730 PRINTF("RPL: Moving parent "); 00731 PRINT6ADDR(&parent->addr); 00732 PRINTF("\n"); 00733 00734 list_remove(dag_src->parents, parent); 00735 parent->dag = dag_dst; 00736 list_add(dag_dst->parents, parent); 00737 } 00738 /************************************************************************/ 00739 rpl_dag_t * 00740 rpl_get_any_dag(void) 00741 { 00742 int i; 00743 00744 for(i = 0; i < RPL_MAX_INSTANCES; ++i) { 00745 if(instance_table[i].used && instance_table[i].current_dag->joined) { 00746 return instance_table[i].current_dag; 00747 } 00748 } 00749 return NULL; 00750 } 00751 /************************************************************************/ 00752 rpl_instance_t * 00753 rpl_get_instance(uint8_t instance_id) 00754 { 00755 int i; 00756 00757 for(i = 0; i < RPL_MAX_INSTANCES; ++i) { 00758 if(instance_table[i].used && instance_table[i].instance_id == instance_id) { 00759 return &instance_table[i]; 00760 } 00761 } 00762 return NULL; 00763 } 00764 /************************************************************************/ 00765 rpl_of_t * 00766 rpl_find_of(rpl_ocp_t ocp) 00767 { 00768 unsigned int i; 00769 00770 for(i = 0; 00771 i < sizeof(objective_functions) / sizeof(objective_functions[0]); 00772 i++) { 00773 if(objective_functions[i]->ocp == ocp) { 00774 return objective_functions[i]; 00775 } 00776 } 00777 00778 return NULL; 00779 } 00780 /************************************************************************/ 00781 void 00782 rpl_join_instance(uip_ipaddr_t *from, rpl_dio_t *dio) 00783 { 00784 rpl_instance_t *instance; 00785 rpl_dag_t *dag; 00786 rpl_parent_t *p; 00787 rpl_of_t *of; 00788 00789 dag = rpl_alloc_dag(dio->instance_id, &dio->dag_id); 00790 if(dag == NULL) { 00791 PRINTF("RPL: Failed to allocate a DAG object!\n"); 00792 return; 00793 } 00794 00795 instance = dag->instance; 00796 00797 p = rpl_add_parent(dag, dio, from); 00798 PRINTF("RPL: Adding "); 00799 PRINT6ADDR(from); 00800 PRINTF(" as a parent: "); 00801 if(p == NULL) { 00802 PRINTF("failed\n"); 00803 instance->used = 0; 00804 return; 00805 } 00806 p->dtsn = dio->dtsn; 00807 PRINTF("succeeded\n"); 00808 00809 /* Determine the objective function by using the 00810 objective code point of the DIO. */ 00811 of = rpl_find_of(dio->ocp); 00812 if(of == NULL) { 00813 PRINTF("RPL: DIO for DAG instance %u does not specify a supported OF\n", 00814 dio->instance_id); 00815 rpl_remove_parent(dag, p); 00816 instance->used = 0; 00817 return; 00818 } 00819 00820 /* Autoconfigure an address if this node does not already have an address 00821 with this prefix. */ 00822 if(dio->prefix_info.flags & UIP_ND6_RA_FLAG_AUTONOMOUS) { 00823 check_prefix(NULL, &dio->prefix_info); 00824 } 00825 00826 dag->joined = 1; 00827 dag->preference = dio->preference; 00828 dag->grounded = dio->grounded; 00829 dag->version = dio->version; 00830 00831 instance->of = of; 00832 instance->mop = dio->mop; 00833 instance->current_dag = dag; 00834 instance->dtsn_out = RPL_LOLLIPOP_INIT; 00835 00836 instance->max_rankinc = dio->dag_max_rankinc; 00837 instance->min_hoprankinc = dio->dag_min_hoprankinc; 00838 instance->dio_intdoubl = dio->dag_intdoubl; 00839 instance->dio_intmin = dio->dag_intmin; 00840 instance->dio_intcurrent = instance->dio_intmin + instance->dio_intdoubl; 00841 instance->dio_redundancy = dio->dag_redund; 00842 instance->default_lifetime = dio->default_lifetime; 00843 instance->lifetime_unit = dio->lifetime_unit; 00844 00845 memcpy(&dag->dag_id, &dio->dag_id, sizeof(dio->dag_id)); 00846 00847 /* Copy prefix information from the DIO into the DAG object. */ 00848 memcpy(&dag->prefix_info, &dio->prefix_info, sizeof(rpl_prefix_t)); 00849 00850 dag->preferred_parent = p; 00851 instance->of->update_metric_container(instance); 00852 dag->rank = instance->of->calculate_rank(p, 0); 00853 /* So far this is the lowest rank we are aware of. */ 00854 dag->min_rank = dag->rank; 00855 00856 if(default_instance == NULL) { 00857 default_instance = instance; 00858 } 00859 00860 PRINTF("RPL: Joined DAG with instance ID %u, rank %hu, DAG ID ", 00861 dio->instance_id, dag->rank); 00862 PRINT6ADDR(&dag->dag_id); 00863 PRINTF("\n"); 00864 00865 ANNOTATE("#A join=%u\n", dag->dag_id.u8[sizeof(dag->dag_id) - 1]); 00866 00867 rpl_reset_dio_timer(instance); 00868 rpl_set_default_route(instance, from); 00869 00870 if(instance->mop != RPL_MOP_NO_DOWNWARD_ROUTES) { 00871 rpl_schedule_dao(instance); 00872 } else { 00873 PRINTF("RPL: The DIO does not meet the prerequisites for sending a DAO\n"); 00874 } 00875 } 00876 00877 /************************************************************************/ 00878 void 00879 rpl_add_dag(uip_ipaddr_t *from, rpl_dio_t *dio) 00880 { 00881 rpl_instance_t *instance; 00882 rpl_dag_t *dag, *previous_dag; 00883 rpl_parent_t *p; 00884 rpl_of_t *of; 00885 00886 dag = rpl_alloc_dag(dio->instance_id, &dio->dag_id); 00887 if(dag == NULL) { 00888 PRINTF("RPL: Failed to allocate a DAG object!\n"); 00889 return; 00890 } 00891 00892 instance = dag->instance; 00893 00894 previous_dag = find_parent_dag(instance, from); 00895 if(previous_dag == NULL) { 00896 PRINTF("RPL: Adding "); 00897 PRINT6ADDR(from); 00898 PRINTF(" as a parent: "); 00899 p = rpl_add_parent(dag, dio, from); 00900 if(p == NULL) { 00901 PRINTF("failed\n"); 00902 dag->used = 0; 00903 return; 00904 } 00905 PRINTF("succeeded\n"); 00906 } else { 00907 p = rpl_find_parent(previous_dag, from); 00908 if(p != NULL) { 00909 rpl_move_parent(previous_dag, dag, p); 00910 } 00911 } 00912 00913 /* Determine the objective function by using the 00914 objective code point of the DIO. */ 00915 of = rpl_find_of(dio->ocp); 00916 if(of != instance->of || 00917 instance->mop != dio->mop || 00918 instance->max_rankinc != dio->dag_max_rankinc || 00919 instance->min_hoprankinc != dio->dag_min_hoprankinc || 00920 instance->dio_intdoubl != dio->dag_intdoubl || 00921 instance->dio_intmin != dio->dag_intmin || 00922 instance->dio_redundancy != dio->dag_redund || 00923 instance->default_lifetime != dio->default_lifetime || 00924 instance->lifetime_unit != dio->lifetime_unit) { 00925 PRINTF("RPL: DIO for DAG instance %u uncompatible with previos DIO\n", 00926 dio->instance_id); 00927 rpl_remove_parent(dag, p); 00928 dag->used = 0; 00929 return; 00930 } 00931 00932 dag->used = 1; 00933 dag->grounded = dio->grounded; 00934 dag->preference = dio->preference; 00935 dag->version = dio->version; 00936 00937 memcpy(&dag->dag_id, &dio->dag_id, sizeof(dio->dag_id)); 00938 00939 /* copy prefix information into the dag */ 00940 memcpy(&dag->prefix_info, &dio->prefix_info, sizeof(rpl_prefix_t)); 00941 00942 dag->preferred_parent = p; 00943 dag->rank = instance->of->calculate_rank(p, 0); 00944 dag->min_rank = dag->rank; /* So far this is the lowest rank we know of. */ 00945 00946 PRINTF("RPL: Joined DAG with instance ID %u, rank %hu, DAG ID ", 00947 dio->instance_id, dag->rank); 00948 PRINT6ADDR(&dag->dag_id); 00949 PRINTF("\n"); 00950 00951 ANNOTATE("#A join=%u\n", dag->dag_id.u8[sizeof(dag->dag_id) - 1]); 00952 00953 rpl_process_parent_event(instance, p); 00954 p->dtsn = dio->dtsn; 00955 } 00956 00957 /************************************************************************/ 00958 static void 00959 global_repair(uip_ipaddr_t *from, rpl_dag_t *dag, rpl_dio_t *dio) 00960 { 00961 rpl_parent_t *p; 00962 00963 remove_parents(dag, 0); 00964 dag->version = dio->version; 00965 dag->instance->of->reset(dag); 00966 dag->min_rank = INFINITE_RANK; 00967 RPL_LOLLIPOP_INCREMENT(dag->instance->dtsn_out); 00968 00969 p = rpl_add_parent(dag, dio, from); 00970 if(p == NULL) { 00971 PRINTF("RPL: Failed to add a parent during the global repair\n"); 00972 dag->rank = INFINITE_RANK; 00973 } else { 00974 dag->rank = dag->instance->of->calculate_rank(p, 0); 00975 dag->min_rank = dag->rank; 00976 rpl_process_parent_event(dag->instance, p); 00977 } 00978 00979 PRINTF("RPL: Participating in a global repair (version=%u, rank=%hu)\n", 00980 dag->version, dag->rank); 00981 00982 RPL_STAT(rpl_stats.global_repairs++); 00983 } 00984 /************************************************************************/ 00985 void 00986 rpl_local_repair(rpl_instance_t *instance) 00987 { 00988 int i; 00989 00990 PRINTF("RPL: Starting a local instance repair\n"); 00991 for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; i++) { 00992 if(instance->dag_table[i].used) { 00993 instance->dag_table[i].rank = INFINITE_RANK; 00994 nullify_parents(&instance->dag_table[i], 0); 00995 } 00996 } 00997 00998 rpl_reset_dio_timer(instance); 00999 01000 RPL_STAT(rpl_stats.local_repairs++); 01001 } 01002 /************************************************************************/ 01003 void 01004 rpl_recalculate_ranks(void) 01005 { 01006 rpl_instance_t *instance, *end; 01007 rpl_parent_t *p; 01008 int i; 01009 01010 /* 01011 * We recalculate ranks when we receive feedback from the system rather 01012 * than RPL protocol messages. This periodical recalculation is called 01013 * from a timer in order to keep the stack depth reasonably low. 01014 */ 01015 for(instance = &instance_table[0], end = instance + RPL_MAX_INSTANCES; instance < end; ++instance) { 01016 if(instance->used) { 01017 for(i = 0; i < RPL_MAX_DAG_PER_INSTANCE; i++) { 01018 if(instance->dag_table[i].used) { 01019 for(p = list_head(instance->dag_table[i].parents); p != NULL; p = p->next) { 01020 if(p->updated) { 01021 p->updated = 0; 01022 if(!rpl_process_parent_event(instance, p)) { 01023 PRINTF("RPL: A parent was dropped\n"); 01024 } 01025 /* 01026 * Stop calculating here because the parent list may have changed. 01027 * If more ranks need to be recalculated, it will be taken care of 01028 * in subsequent calls to this functions. 01029 */ 01030 break; 01031 } 01032 } 01033 } 01034 } 01035 } 01036 } 01037 } 01038 /************************************************************************/ 01039 int 01040 rpl_process_parent_event(rpl_instance_t *instance, rpl_parent_t *p) 01041 { 01042 rpl_rank_t old_rank; 01043 int return_value; 01044 01045 old_rank = instance->current_dag->rank; 01046 return_value = 1; 01047 01048 if(!acceptable_rank(p->dag, p->rank)) { 01049 /* The candidate parent is no longer valid: the rank increase resulting 01050 from the choice of it as a parent would be too high. */ 01051 PRINTF("RPL: Unacceptable rank %u\n", (unsigned)p->rank); 01052 if(p != instance->current_dag->preferred_parent) { 01053 rpl_nullify_parent(p->dag, p); 01054 return 0; 01055 } else { 01056 rpl_nullify_parent(p->dag, p); 01057 return_value = 0; 01058 } 01059 } 01060 01061 if(rpl_select_dag(instance, p) == NULL) { 01062 /* No suitable parent; trigger a local repair. */ 01063 PRINTF("RPL: No parents found in any DAG\n"); 01064 rpl_local_repair(instance); 01065 return 0; 01066 } 01067 01068 #if DEBUG 01069 if(DAG_RANK(old_rank, instance) != DAG_RANK(instance->current_dag->rank, instance)) { 01070 PRINTF("RPL: Moving in the instance from rank %hu to %hu\n", 01071 DAG_RANK(old_rank, instance), DAG_RANK(instance->current_dag->rank, instance)); 01072 if(instance->current_dag->rank != INFINITE_RANK) { 01073 PRINTF("RPL: The preferred parent is "); 01074 PRINT6ADDR(&instance->current_dag->preferred_parent->addr); 01075 PRINTF(" (rank %u)\n", 01076 (unsigned)DAG_RANK(instance->current_dag->preferred_parent->rank, instance)); 01077 } else { 01078 PRINTF("RPL: We don't have any parent"); 01079 } 01080 } 01081 #endif /* DEBUG */ 01082 01083 return return_value; 01084 } 01085 /************************************************************************/ 01086 void 01087 rpl_process_dio(uip_ipaddr_t *from, rpl_dio_t *dio) 01088 { 01089 rpl_instance_t *instance; 01090 rpl_dag_t *dag, *previous_dag; 01091 rpl_parent_t *p; 01092 01093 if(dio->mop != RPL_MOP_DEFAULT) { 01094 PRINTF("RPL: Ignoring a DIO with an unsupported MOP: %d\n", dio->mop); 01095 return; 01096 } 01097 01098 if(dio->rank == INFINITE_RANK) { 01099 PRINTF("RPL: Ignoring DIO from node with infinite rank: "); 01100 PRINT6ADDR(from); 01101 PRINTF("\n"); 01102 return; 01103 } 01104 01105 instance = rpl_get_instance(dio->instance_id); 01106 if(instance == NULL) { 01107 PRINTF("RPL: New instance detected: Joining...\n"); 01108 rpl_join_instance(from, dio); 01109 return; 01110 } 01111 01112 dag = get_dag(dio->instance_id, &dio->dag_id); 01113 if(dag == NULL) { 01114 PRINTF("RPL: Adding new DAG to known instance.\n"); 01115 rpl_add_dag(from, dio); 01116 return; 01117 } 01118 01119 if(lollipop_greater_than(dio->version, dag->version)) { 01120 if(dag->rank == ROOT_RANK(instance)) { 01121 PRINTF("RPL: Root received inconsistent DIO version number\n"); 01122 dag->version = dio->version; 01123 RPL_LOLLIPOP_INCREMENT(dag->version); 01124 rpl_reset_dio_timer(instance); 01125 } else { 01126 global_repair(from, dag, dio); 01127 } 01128 return; 01129 } 01130 01131 if(lollipop_greater_than(dag->version, dio->version)) { 01132 /* The DIO sender is on an older version of the DAG. */ 01133 PRINTF("RPL: old version received => inconsistency detected\n"); 01134 if(dag->joined) { 01135 rpl_reset_dio_timer(instance); 01136 return; 01137 } 01138 } 01139 01140 if(dio->rank < ROOT_RANK(instance)) { 01141 PRINTF("RPL: Ignoring DIO with too low rank: %u\n", 01142 (unsigned)dio->rank); 01143 return; 01144 } else if(dio->rank == INFINITE_RANK && dag->joined) { 01145 rpl_reset_dio_timer(instance); 01146 } 01147 01148 if(dag->rank == ROOT_RANK(instance)) { 01149 if(dio->rank != INFINITE_RANK) { 01150 instance->dio_counter++; 01151 } 01152 return; 01153 } 01154 01155 /* 01156 * At this point, we know that this DIO pertains to a DAG that 01157 * we are already part of. We consider the sender of the DIO to be 01158 * a candidate parent, and let rpl_process_parent_event decide 01159 * whether to keep it in the set. 01160 */ 01161 01162 p = rpl_find_parent(dag, from); 01163 if(p == NULL) { 01164 previous_dag = find_parent_dag(instance, from); 01165 if(previous_dag == NULL) { 01166 if(RPL_PARENT_COUNT(dag) == RPL_MAX_PARENTS_PER_DAG) { 01167 /* Make room for a new parent. */ 01168 remove_worst_parent(dag, dio->rank); 01169 } 01170 /* Add the DIO sender as a candidate parent. */ 01171 p = rpl_add_parent(dag, dio, from); 01172 if(p == NULL) { 01173 PRINTF("RPL: Failed to add a new parent ("); 01174 PRINT6ADDR(from); 01175 PRINTF(")\n"); 01176 return; 01177 } 01178 PRINTF("RPL: New candidate parent with rank %u: ", (unsigned)p->rank); 01179 PRINT6ADDR(from); 01180 PRINTF("\n"); 01181 } else { 01182 p = rpl_find_parent(previous_dag, from); 01183 if(p != NULL) { 01184 rpl_move_parent(previous_dag, dag, p); 01185 } 01186 } 01187 } else { 01188 if(p->rank == dio->rank) { 01189 PRINTF("RPL: Received consistent DIO\n"); 01190 if(dag->joined) { 01191 instance->dio_counter++; 01192 } 01193 } else { 01194 p->rank=dio->rank; 01195 } 01196 } 01197 01198 PRINTF("RPL: preferred DAG "); 01199 PRINT6ADDR(&instance->current_dag->dag_id); 01200 PRINTF(", rank %u, min_rank %u, ", 01201 instance->current_dag->rank, instance->current_dag->min_rank); 01202 PRINTF("parent rank %u, parent etx %u, link metric %u, instance etx %u\n", 01203 p->rank, p->mc.obj.etx, p->link_metric, instance->mc.obj.etx); 01204 01205 /* We have allocated a candidate parent; process the DIO further. */ 01206 01207 memcpy(&p->mc, &dio->mc, sizeof(p->mc)); 01208 if(rpl_process_parent_event(instance, p) == 0) { 01209 PRINTF("RPL: The candidate parent is rejected\n"); 01210 return; 01211 } 01212 01213 /* We don't use route control, so we can have only one official parent. */ 01214 if(dag->joined && p == dag->preferred_parent) { 01215 if(should_send_dao(instance, dio, p)) { 01216 RPL_LOLLIPOP_INCREMENT(instance->dtsn_out); 01217 rpl_schedule_dao(instance); 01218 } 01219 } 01220 p->dtsn = dio->dtsn; 01221 } 01222 /************************************************************************/