rpl_upward.c

00001 /*
00002  * Copyright (c) 2015-2019, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License");
00006  * you may not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  *     http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 
00018 /* rpl_upward.c deals with management of the DODAG and upward routes within an
00019  * instance.
00020  *
00021  * rpl_domain_t is accessible, but not normally manipulated - all routines in
00022  * this file works on a specific instance.
00023  *
00024  * rpl_instance_t, rpl_dodag_t, rpl_dodag_version_t, rpl_neighbour_t are all accessible.
00025  */
00026 
00027 #include "nsconfig.h"
00028 
00029 #ifdef HAVE_RPL
00030 #include "ns_types.h"
00031 #include "ns_list.h"
00032 #include "ns_trace.h"
00033 #include "common_functions.h"
00034 #include "randLIB.h"
00035 #include "nsdynmemLIB.h"
00036 #include <string.h>
00037 #include "ip6string.h"
00038 
00039 #include "net_interface.h"
00040 
00041 #include "Core/include/ns_address_internal.h"
00042 #include "Common_Protocols/icmpv6.h"
00043 #include "Common_Protocols/icmpv6_prefix.h"
00044 #include "NWK_INTERFACE/Include/protocol_abstract.h"
00045 #include "NWK_INTERFACE/Include/protocol_stats.h"
00046 #include "Service_Libs/Trickle/trickle.h"
00047 #include "ipv6_stack/ipv6_routing_table.h"
00048 #include "6LoWPAN/Bootstraps/protocol_6lowpan.h"
00049 #include "Common_Protocols/ipv6_resolution.h"
00050 
00051 #include "RPL/rpl_protocol.h"
00052 #include "RPL/rpl_policy.h"
00053 #include "RPL/rpl_control.h"
00054 #include "RPL/rpl_objective.h"
00055 #include "RPL/rpl_upward.h"
00056 #include "RPL/rpl_downward.h"
00057 #include "RPL/rpl_structures.h"
00058 
00059 #include "net_rpl.h"
00060 
00061 #define TRACE_GROUP "rplu"
00062 
00063 /* How many times to transmit/retransmit a zero-lifetime route */
00064 #define RPL_MAX_FINAL_RTR_ADVERTISEMENTS 3
00065 
00066 #define RPL_DEFAULT_DIO_INTERVAL_MIN 3
00067 #define RPL_DEFAULT_DIO_INTERVAL_DOUBLINGS 20
00068 
00069 #define RPL_DEFAULT_IMIN_TICKS (((1ull << RPL_DEFAULT_DIO_INTERVAL_MIN) + 99) / 100)
00070 #define RPL_DEFAULT_IMAX_TICKS (((1ull << (RPL_DEFAULT_DIO_INTERVAL_MIN+RPL_DEFAULT_DIO_INTERVAL_DOUBLINGS)) + 99) / 100)
00071 
00072 static NS_LIST_DEFINE(rpl_candidate_neighbour_set, rpl_neighbour_t, candidate_neighbour_link);
00073 
00074 static void rpl_instance_remove_parents(rpl_instance_t *instance);
00075 static void rpl_instance_remove_system_routes_through_parent(rpl_instance_t *instance, rpl_neighbour_t *parent);
00076 static void rpl_dodag_update_system_route(rpl_dodag_t *dodag, rpl_dio_route_t *route);
00077 
00078 /* Rank comparison, and DAGRank(rank) */
00079 uint16_t nrpl_dag_rank(const rpl_dodag_t *dodag, uint16_t rank)
00080 {
00081     return rank == RPL_RANK_INFINITE ? rank : rank / dodag->config.min_hop_rank_increase;
00082 }
00083 
00084 uint16_t nrpl_rank(const rpl_dodag_t *dodag, uint16_t dag_rank)
00085 {
00086     uint32_t rank = (uint32_t) dag_rank * dodag->config.min_hop_rank_increase;
00087     return rank < RPL_RANK_INFINITE ? rank : RPL_RANK_INFINITE;
00088 }
00089 
00090 /* Silly function needed because RPL HbH option includes dagrank directly */
00091 rpl_cmp_t rpl_rank_compare_dagrank_rank(const rpl_dodag_t *dodag, uint16_t dag_rank_a, uint16_t b)
00092 {
00093     /* Special infinity handling makes sure we're absolutely solid, but callers
00094      * do need to then consider the (faint) possibility of unordered.
00095      */
00096     if (dag_rank_a == RPL_RANK_INFINITE) {
00097         return b == RPL_RANK_INFINITE ? RPL_CMP_UNORDERED : RPL_CMP_GREATER;
00098     } else if (b == RPL_RANK_INFINITE) {
00099         return RPL_CMP_LESS;
00100     }
00101 
00102     if (!dodag) {
00103         return RPL_CMP_UNORDERED;
00104     }
00105 
00106     uint16_t dag_rank_b = nrpl_dag_rank(dodag, b);
00107     if (dag_rank_a < dag_rank_b) {
00108         return RPL_CMP_LESS;
00109     } else if (dag_rank_a == dag_rank_b) {
00110         return RPL_CMP_EQUAL;
00111     } else {
00112         return RPL_CMP_GREATER;
00113     }
00114 }
00115 
00116 rpl_cmp_t rpl_rank_compare(const rpl_dodag_t *dodag, uint16_t a, uint16_t b)
00117 {
00118     uint16_t dag_rank_a = nrpl_dag_rank(dodag, a);
00119     return rpl_rank_compare_dagrank_rank(dodag, dag_rank_a, b);
00120 }
00121 
00122 /* Given a Rank, round up to the next higher integral rank */
00123 uint16_t rpl_rank_next_level(const rpl_dodag_t *dodag, uint16_t a)
00124 {
00125     uint16_t r = dodag->config.min_hop_rank_increase * (1 + nrpl_dag_rank(dodag, a));
00126     return r >= a ? r : RPL_RANK_INFINITE;
00127 }
00128 
00129 /* Given a Rank, return the maximum Rank with equal DAGRank */
00130 uint16_t rpl_rank_max_at_level(const rpl_dodag_t *dodag, uint16_t a)
00131 {
00132     uint16_t r = dodag->config.min_hop_rank_increase * (1 + nrpl_dag_rank(dodag, a)) - 1;
00133     return r >= a ? r : RPL_RANK_INFINITE;
00134 }
00135 
00136 /* Add two ranks, checking for overflow */
00137 uint16_t rpl_rank_add(uint16_t a, uint16_t b)
00138 {
00139     uint16_t r = a + b;
00140     return r >= a ? r : RPL_RANK_INFINITE;
00141 }
00142 
00143 /* Subtract two ranks, checking for overflow */
00144 uint16_t rpl_rank_sub(uint16_t a, uint16_t b)
00145 {
00146     uint16_t r = a - b;
00147     return r <= a ? r : 0;
00148 }
00149 
00150 /* Sequence counter operations (RFC 6550 S7.2) */
00151 #define RPL_SEQUENCE_WINDOW 16
00152 
00153 uint8_t rpl_seq_init(void)
00154 {
00155     return 256 - RPL_SEQUENCE_WINDOW;
00156 }
00157 
00158 uint8_t rpl_seq_inc(uint8_t seq)
00159 {
00160     return seq == 127 ? 0 : (uint8_t)(seq + 1);
00161 }
00162 
00163 rpl_cmp_t rpl_seq_compare(uint8_t a, uint8_t b)
00164 {
00165     if (a == b) {
00166         return RPL_CMP_EQUAL;
00167     } else if (a >= 128 && b < 128) {
00168         if (256 + b - a <= RPL_SEQUENCE_WINDOW) {
00169             return RPL_CMP_LESS;
00170         } else {
00171             return RPL_CMP_GREATER;
00172         }
00173     } else if (b >= 128 && a < 128) {
00174         if (256 + a - b <= RPL_SEQUENCE_WINDOW) {
00175             return RPL_CMP_GREATER;
00176         } else {
00177             return RPL_CMP_LESS;
00178         }
00179     } else if (a < 128) { /* so both <= 127 */
00180         /* RFC 6550 description is wrong/misleading ("If the absolute magnitude
00181          * of difference between the two sequence counters is less than or
00182          * equal to SEQUENCE_WINDOW...)". This doesn't cover the wrap
00183          * at the end of the circular region - the difference has to
00184          * be computed modulo-128..
00185          */
00186         uint8_t diff = (a - b) & 127;
00187         if (diff <= RPL_SEQUENCE_WINDOW) {
00188             return RPL_CMP_GREATER;
00189         } else if (diff >= 128 - RPL_SEQUENCE_WINDOW) {
00190             return RPL_CMP_LESS;
00191         } else {
00192             return RPL_CMP_UNORDERED;
00193         }
00194     } else { /* both >= 128 */
00195         /* In this case, there's no wrap, so absolute difference being bigger
00196          * than SEQUENCE_WINDOW is unordered, as the RFC says (230 could be
00197          * newer than 250 due to reboot, or could be old).
00198          */
00199         uint8_t abs_diff = a > b ? a - b : b - a;
00200         if (abs_diff > RPL_SEQUENCE_WINDOW) {
00201             return RPL_CMP_UNORDERED;
00202         } else if (a > b) {
00203             return RPL_CMP_GREATER;
00204         } else {
00205             return RPL_CMP_LESS;
00206         }
00207     }
00208 }
00209 
00210 void rpl_instance_set_dodag_version(rpl_instance_t *instance, rpl_dodag_version_t *version, uint16_t rank)
00211 {
00212     if (!version || rpl_dodag_am_leaf(version->dodag)) {
00213         if (!version) {
00214             tr_debug("No version -> set RPL_RANK_INFINITE");
00215         } else {
00216             tr_debug("Leaf -> set RPL_RANK_INFINITE");
00217         }
00218         rank = RPL_RANK_INFINITE;
00219     }
00220 
00221     instance->current_rank = rank;
00222 
00223     rpl_dodag_version_t *old_version = instance->current_dodag_version;
00224     if (old_version == version) {
00225         return;
00226     }
00227 
00228     instance->current_dodag_version = version;
00229     if (version) {
00230         version->dodag->used = true;
00231         if (version->dodag->root) {
00232             rpl_instance_remove_parents(instance);
00233         }
00234 
00235         /* Need to call trickle_start somewhere (to avoid uninitialised variables) - this is it */
00236         if (!old_version || old_version->dodag != version->dodag) {
00237             trickle_start(&instance->dio_timer, &version->dodag->dio_timer_params);
00238         }
00239     }
00240 
00241     /* Then changing dodag version is an inconsistency. We may be changing from non-NULL to NULL, in which case we use old parameters to do poison */
00242     trickle_inconsistent_heard(&instance->dio_timer, version ? &version->dodag->dio_timer_params : &old_version->dodag->dio_timer_params);
00243 }
00244 
00245 rpl_dodag_version_t *rpl_instance_current_dodag_version(const rpl_instance_t *instance)
00246 {
00247     return instance->current_dodag_version;
00248 }
00249 
00250 rpl_dodag_t *rpl_instance_current_dodag(const rpl_instance_t *instance)
00251 {
00252     return instance->current_dodag_version ? instance->current_dodag_version->dodag : NULL;
00253 }
00254 
00255 #ifdef HAVE_RPL_ROOT
00256 bool rpl_instance_am_root(const rpl_instance_t *instance)
00257 {
00258     rpl_dodag_t *dodag = rpl_instance_current_dodag(instance);
00259     return dodag ? rpl_dodag_am_root(dodag) : false;
00260 }
00261 #endif
00262 
00263 uint8_t rpl_instance_mop(const rpl_instance_t *instance)
00264 {
00265     rpl_dodag_t *dodag = rpl_instance_current_dodag(instance);
00266     /* MOP is supposed to be the same for all DODAGs, so take any */
00267     if (!dodag) {
00268         dodag = ns_list_get_first(&instance->dodags);
00269     }
00270     return dodag ? rpl_dodag_mop(dodag) : RPL_MODE_NO_DOWNWARD;
00271 }
00272 
00273 rpl_neighbour_t *rpl_instance_preferred_parent(const rpl_instance_t *instance)
00274 {
00275     /* DODAG parents are first in the neighbour list, and preferred is first.
00276      * So if we have a preferred parent, it's the first entry, and its
00277      * dodag_parent (or was_dodag_parent) flag is set.
00278      */
00279     rpl_neighbour_t *neighbour = ns_list_get_first(&instance->candidate_neighbours);
00280     if (!neighbour || (!neighbour->dodag_parent && !neighbour->was_dodag_parent)) {
00281         return NULL;
00282     }
00283     return neighbour;
00284 }
00285 
00286 /* If we're a member of a DODAG Version matching the predicate in this instance,
00287  * return it. Mainly used for handling DODAG Information Solicitations.
00288  */
00289 rpl_dodag_version_t *rpl_instance_predicate_match(rpl_instance_t *instance, uint8_t pred, uint8_t instance_id, const uint8_t *dodagid, uint8_t version_num)
00290 {
00291     rpl_dodag_version_t *dodag_version = instance->current_dodag_version;
00292     if (!dodag_version) {
00293         return NULL;
00294     }
00295     if ((pred & RPL_SOLINFO_PRED_INSTANCEID) && (instance->id != instance_id)) {
00296         return NULL;
00297     }
00298     if ((pred & RPL_SOLINFO_PRED_DODAGID) && !addr_ipv6_equal(dodag_version->dodag->id, dodagid)) {
00299         return NULL;
00300     }
00301     if ((pred & RPL_SOLINFO_PRED_VERSION) && dodag_version->number != version_num) {
00302         return NULL;
00303     }
00304     return dodag_version;
00305 }
00306 
00307 void rpl_instance_inconsistency(rpl_instance_t *instance)
00308 {
00309     if (instance->current_dodag_version) {
00310         trickle_inconsistent_heard(&instance->dio_timer, &instance->current_dodag_version->dodag->dio_timer_params);
00311     }
00312 }
00313 
00314 void rpl_instance_consistent_rx(rpl_instance_t *instance)
00315 {
00316     if (!instance->dio_not_consistent) {
00317         trickle_consistent_heard(&instance->dio_timer);
00318     }
00319 }
00320 
00321 void rpl_instance_increment_dtsn(rpl_instance_t *instance)
00322 {
00323     instance->dtsn = rpl_seq_inc(instance->dtsn);
00324     instance->last_dao_trigger_time = protocol_core_monotonic_time;
00325     instance->srh_error_count = 0;
00326     /* Should a DTSN increment trigger DIOs, thus? */
00327     rpl_instance_inconsistency(instance);
00328 }
00329 
00330 void rpl_instance_poison(rpl_instance_t *instance, uint8_t count)
00331 {
00332     if (instance->poison_count < count) {
00333         instance->poison_count = count;
00334     }
00335     rpl_instance_inconsistency(instance);
00336 }
00337 
00338 void rpl_instance_force_leaf(rpl_instance_t *instance)
00339 {
00340     instance->current_rank = RPL_RANK_INFINITE;
00341 }
00342 
00343 void rpl_instance_trigger_parent_selection(rpl_instance_t *instance, uint16_t delay)
00344 {
00345     if (instance->parent_selection_timer == 0 || instance->parent_selection_timer > delay) {
00346         instance->parent_selection_timer = randLIB_randomise_base(delay, 0x7333, 0x8CCD) /* +/- 10% */;
00347     }
00348 }
00349 
00350 static void rpl_instance_parent_selection_timer(rpl_instance_t *instance, uint16_t seconds)
00351 {
00352 
00353 
00354     if (instance->parent_selection_timer > seconds) {
00355         instance->parent_selection_timer -= seconds;
00356     } else if (instance->parent_selection_timer != 0) {
00357         tr_debug("Timed parent selection");
00358         rpl_instance_run_parent_selection(instance);
00359     }
00360 }
00361 
00362 rpl_dodag_t *rpl_lookup_dodag(const rpl_instance_t *instance, const uint8_t *dodagid)
00363 {
00364     ns_list_foreach(rpl_dodag_t, dodag, &instance->dodags) {
00365         if (addr_ipv6_equal(dodag->id, dodagid)) {
00366             dodag->timestamp = protocol_core_monotonic_time;
00367             return dodag;
00368         }
00369     }
00370     return NULL;
00371 }
00372 
00373 rpl_dodag_version_t *rpl_lookup_dodag_version(const rpl_dodag_t *dodag, uint8_t version_num)
00374 {
00375     ns_list_foreach(rpl_dodag_version_t, dodag_version, &dodag->versions) {
00376         if (dodag_version->number == version_num) {
00377             return dodag_version;
00378         }
00379     }
00380     return NULL;
00381 }
00382 
00383 rpl_neighbour_t *rpl_lookup_neighbour_by_ll_address(const rpl_instance_t *instance, const uint8_t *addr, int8_t if_id)
00384 {
00385     ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
00386         if (neighbour->interface_id == if_id && addr_ipv6_equal(neighbour->ll_address, addr)) {
00387             return neighbour;
00388         }
00389     }
00390     return NULL;
00391 }
00392 
00393 rpl_neighbour_t *rpl_create_neighbour(rpl_dodag_version_t *version, const uint8_t *addr, int8_t if_id, uint8_t g_mop_prf, uint8_t dtsn)
00394 {
00395     /* Should gate higher-rank neighbours here - ignore higher-rank neighbours
00396      * unless in some sort of local repair.
00397      */
00398 
00399     rpl_neighbour_t *neighbour = rpl_alloc(sizeof(rpl_neighbour_t));
00400     if (!neighbour) {
00401         return NULL;
00402     }
00403 
00404     rpl_instance_t *instance = version->dodag->instance;
00405     neighbour->dodag_version = version;
00406     memcpy(neighbour->ll_address, addr, 16);
00407     memset(neighbour->global_address, 0, 16);
00408     neighbour->have_global_address = false;
00409     neighbour->dodag_parent = neighbour->was_dodag_parent = false;
00410     neighbour->considered = false;
00411     neighbour->interface_id = if_id;
00412     neighbour->rank = 0xffff;
00413     neighbour->g_mop_prf = g_mop_prf;
00414     neighbour->dtsn = dtsn;
00415     neighbour->dao_path_control = 0;
00416     neighbour->confirmed = 0;
00417 
00418     /* Need to limit number of neighbours here - chucking worst neighbour */
00419 
00420     /* Neighbour list wants parents at the front of the list; slot new
00421      * people in after the parents. Then old neighbours get pushed to the end.
00422      */
00423     ns_list_foreach(rpl_neighbour_t, n, &instance->candidate_neighbours) {
00424         if (!n->dodag_parent) {
00425             ns_list_add_before(&instance->candidate_neighbours, n, neighbour);
00426             return neighbour;
00427         }
00428     }
00429     ns_list_add_to_end(&instance->candidate_neighbours, neighbour);
00430     return neighbour;
00431 }
00432 
00433 void rpl_delete_neighbour(rpl_instance_t *instance, rpl_neighbour_t *neighbour)
00434 {
00435     rpl_dao_target_t *dao_target = rpl_instance_get_active_target_confirmation(instance);
00436     if (dao_target && instance->wait_response == neighbour) {
00437         instance->wait_response = NULL;
00438     }
00439 
00440     rpl_downward_neighbour_gone(instance, neighbour);
00441     ns_list_remove(&instance->candidate_neighbours, neighbour);
00442     if (neighbour->dao_path_control) {
00443     }
00444     if (neighbour->dodag_parent) {
00445         rpl_instance_remove_system_routes_through_parent(instance, neighbour);
00446         rpl_instance_neighbours_changed(instance, NULL);
00447     }
00448 
00449     rpl_free(neighbour, sizeof * neighbour);
00450 }
00451 
00452 const uint8_t *rpl_neighbour_ll_address(const rpl_neighbour_t *neighbour)
00453 {
00454     return neighbour->ll_address;
00455 }
00456 
00457 const uint8_t *rpl_neighbour_global_address(const rpl_neighbour_t *neighbour)
00458 {
00459     return neighbour->have_global_address ? neighbour->global_address : NULL;
00460 }
00461 
00462 void rpl_neighbour_update_global_address(rpl_neighbour_t *neighbour, const uint8_t *addr)
00463 {
00464     if (!addr_ipv6_equal(neighbour->global_address, addr)) {
00465         memcpy(neighbour->global_address, addr, 16);
00466         neighbour->have_global_address = true;
00467         //neighbour->down_change = true;
00468     }
00469 }
00470 
00471 void rpl_neighbour_update_dodag_version(rpl_neighbour_t *neighbour, rpl_dodag_version_t *version, uint16_t rank, uint8_t g_mop_prf)
00472 {
00473     /* DODAG follows G/MOP/Prf of preferred parent if it isn't moving */
00474     if (g_mop_prf != version->dodag->g_mop_prf &&
00475             (rpl_dodag_version_compare(version, neighbour->dodag_version) & (RPL_CMP_GREATER | RPL_CMP_EQUAL)) &&
00476             neighbour == rpl_instance_preferred_parent(version->dodag->instance)) {
00477         version->dodag->g_mop_prf = g_mop_prf;
00478         rpl_dodag_inconsistency(version->dodag);
00479     }
00480     neighbour->g_mop_prf = g_mop_prf;
00481     neighbour->dodag_version = version;
00482     neighbour->rank = rank;
00483     neighbour->dio_timestamp = protocol_core_monotonic_time;
00484 }
00485 
00486 bool rpl_neighbour_update_dtsn(rpl_neighbour_t *neighbour, uint8_t dtsn)
00487 {
00488     uint8_t old_dtsn = neighbour->dtsn;
00489 
00490     neighbour->dtsn = dtsn;
00491 
00492     return neighbour->dodag_parent && (rpl_seq_compare(dtsn, old_dtsn) & RPL_CMP_GREATER);
00493 }
00494 
00495 rpl_instance_t *rpl_neighbour_instance(const rpl_neighbour_t *neighbour)
00496 {
00497     return neighbour->dodag_version->dodag->instance;
00498 }
00499 
00500 rpl_dodag_version_t *rpl_create_dodag_version(rpl_dodag_t *dodag, uint8_t version_num)
00501 {
00502     rpl_dodag_version_t *version = rpl_alloc(sizeof(rpl_dodag_version_t));
00503     if (!version) {
00504         return NULL;
00505     }
00506 
00507     version->dodag = dodag;
00508     version->number = version_num;
00509     version->last_advertised_rank = RPL_RANK_INFINITE;
00510     version->lowest_advertised_rank = RPL_RANK_INFINITE;
00511     version->greediness_rank_limit = RPL_RANK_INFINITE;
00512     version->hard_rank_limit = RPL_RANK_INFINITE;
00513 
00514     if (!ns_list_is_empty(&dodag->versions)) {
00515         protocol_stats_update(STATS_RPL_GLOBAL_REPAIR, 1);
00516     }
00517 
00518     /* Maintain the version list newest first, taking care on ordering */
00519     bool inserted = false;
00520     ns_list_foreach_safe(rpl_dodag_version_t, v, &dodag->versions) {
00521         rpl_cmp_t cmp = rpl_seq_compare(version_num, v->number);
00522         if (cmp & (RPL_CMP_GREATER | RPL_CMP_UNORDERED)) {
00523             /* "Unordered" is treated as newest (as per RFC 6550 7.2 rule 4?) */
00524             ns_list_add_before(&dodag->versions, v, version);
00525             inserted = true;
00526             break;
00527         }
00528     }
00529     if (!inserted) {
00530         ns_list_add_to_end(&dodag->versions, version);
00531     }
00532 
00533     /* Now a clean-up to guarantee we have a completely comparable list.
00534      * Starting from the newest, check every other element is "less" than the
00535      * newest. If we hit one that isn't, chuck that, and all subsequent ones.
00536      */
00537     rpl_dodag_version_t *newest = ns_list_get_first(&dodag->versions);
00538     for (rpl_dodag_version_t *v = ns_list_get_next(&dodag->versions, newest); v; v = ns_list_get_next(&dodag->versions, v)) {
00539         if (rpl_seq_compare(v->number, newest->number) & RPL_CMP_LESS) {
00540             continue;
00541         } else {
00542             do {
00543                 rpl_dodag_version_t *next = ns_list_get_next(&dodag->versions, v);
00544                 rpl_delete_dodag_version(v);
00545                 v = next;
00546             } while (v);
00547             break;
00548         }
00549     }
00550 
00551 
00552 
00553     return version;
00554 }
00555 
00556 void rpl_delete_dodag_version(rpl_dodag_version_t *version)
00557 {
00558     rpl_dodag_t *dodag = version->dodag;
00559     rpl_instance_t *instance = dodag->instance;
00560 
00561     if (instance->current_dodag_version == version) {
00562         // Don't call rpl_instance_set_dodag_version(NULL) - that would pre-empt parent reselection,
00563         // triggering poison immediately.
00564         // Give parent selection a chance to select another version (but will it have any info on-hand?)
00565         instance->current_dodag_version = NULL;
00566         rpl_instance_trigger_parent_selection(instance, 5);
00567     }
00568 
00569     ns_list_foreach_safe(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
00570         if (neighbour->dodag_version == version) {
00571             rpl_delete_neighbour(instance, neighbour);
00572         }
00573     }
00574     ns_list_remove(&dodag->versions, version);
00575     rpl_free(version, sizeof(*version));
00576 }
00577 
00578 bool rpl_dodag_version_is_current(const rpl_dodag_version_t *version)
00579 {
00580     return version->dodag->instance->current_dodag_version == version;
00581 }
00582 
00583 bool rpl_dodag_version_rank_indicates_possible_sub_dodag(const rpl_dodag_version_t *version, uint16_t rank)
00584 {
00585     if (!rpl_dodag_version_is_current(version)) {
00586         return false;
00587     }
00588     rpl_cmp_t cmp = rpl_rank_compare(version->dodag, rank, version->dodag->instance->current_rank);
00589     return cmp & RPL_CMP_GREATER;
00590 }
00591 
00592 rpl_cmp_t rpl_dodag_version_compare(const rpl_dodag_version_t *a, const rpl_dodag_version_t *b)
00593 {
00594     if (a == NULL || b == NULL) {
00595         return RPL_CMP_UNORDERED;
00596     }
00597     if (a == b) {
00598         return RPL_CMP_EQUAL;
00599     }
00600     if (a->dodag != b->dodag) {
00601         return RPL_CMP_UNORDERED;
00602     }
00603     return rpl_seq_compare(a->number, b->number);
00604 }
00605 
00606 void rpl_dodag_version_limit_greediness(rpl_dodag_version_t *version, uint16_t rank)
00607 {
00608     /* Apply RPL greediness limit rule - after we've joined a DODAG version,
00609      * we don't increase rank unless required to by an existing parent.
00610      */
00611     if (rank != RPL_RANK_INFINITE && version->greediness_rank_limit == RPL_RANK_INFINITE) {
00612         version->greediness_rank_limit = rpl_rank_max_at_level(version->dodag, rank);
00613     }
00614 }
00615 
00616 void rpl_dodag_version_raise_greediness(rpl_dodag_version_t *version, uint16_t pref_rank)
00617 {
00618     /* This can be called during parent selection, after preferred parent is chosen,
00619      * to potentially increase the greediness limit considering the new parent circumstance.
00620      * Eg, if our initial and current Rank was 1, our greediness limit would have
00621      * been 1.99. But if we've just had to increase Rank to 2 for an existing
00622      * parent, then we can raise the limit.
00623      */
00624     if (version->greediness_rank_limit < pref_rank) {
00625         version->greediness_rank_limit = rpl_rank_max_at_level(version->dodag, pref_rank);
00626     }
00627 }
00628 
00629 rpl_dodag_t *rpl_create_dodag(rpl_instance_t *instance, const uint8_t *dodagid, uint8_t g_mop_prf)
00630 {
00631     rpl_dodag_t *dodag = rpl_alloc(sizeof(rpl_dodag_t));
00632     if (!dodag) {
00633         return NULL;
00634     }
00635 
00636     dodag->instance = instance;
00637     dodag->timestamp = protocol_core_monotonic_time;
00638     memcpy(dodag->id, dodagid, 16);
00639     dodag->leaf = false;
00640     dodag->root = false;
00641     dodag->have_config = false;
00642     dodag->used = false;
00643     dodag->g_mop_prf = g_mop_prf;
00644     dodag->new_config_advertisment_count = 0;
00645     // Default timer parameters and trickle start should never normally
00646     // be used - we would set the parameters from the DODAG Config and start
00647     // as we join a version. But initialising here catches odd cases where
00648     // we end up sending poison DIOs before we get any config.
00649     dodag->dio_timer_params.Imin = RPL_DEFAULT_IMIN_TICKS;
00650     dodag->dio_timer_params.Imax = (trickle_time_t)(RPL_DEFAULT_IMAX_TICKS < TRICKLE_TIME_MAX ? RPL_DEFAULT_IMAX_TICKS : TRICKLE_TIME_MAX);
00651     dodag->dio_timer_params.k = 10;
00652     trickle_start(&instance->dio_timer, &dodag->dio_timer_params);
00653     ns_list_init(&dodag->versions);
00654     ns_list_init(&dodag->routes);
00655     ns_list_init(&dodag->prefixes);
00656 
00657     ns_list_add_to_start(&instance->dodags, dodag);
00658     return dodag;
00659 }
00660 
00661 void rpl_delete_dodag(rpl_dodag_t *dodag)
00662 {
00663     rpl_instance_t *instance = dodag->instance;
00664     ns_list_foreach_safe(rpl_dodag_version_t, version, &dodag->versions) {
00665         rpl_delete_dodag_version(version);
00666     }
00667     ns_list_foreach_safe(rpl_dio_route_t, route, &dodag->routes) {
00668         rpl_dodag_delete_dio_route(dodag, route);
00669     }
00670     ns_list_foreach_safe(prefix_entry_t, prefix, &dodag->prefixes) {
00671         rpl_dodag_delete_dio_prefix(dodag, prefix);
00672     }
00673     ns_list_remove(&instance->dodags, dodag);
00674     rpl_free(dodag, sizeof(*dodag));
00675 }
00676 
00677 void rpl_delete_dodag_root(rpl_dodag_t *dodag)
00678 {
00679     // This should trigger immediate poison
00680     rpl_instance_set_dodag_version(dodag->instance, NULL, RPL_RANK_INFINITE);
00681     // Deleting DODAG is not ideal - we will just pick up adverts from our
00682     // former children, and recreate, possibly violating the MaxRankIncrease.
00683     // Should retain DODAG version info and just unset root flag, which will
00684     // limit what happens when we hear adverts.
00685     // Problem is rpl_control_create_dodag_root which can't handle the
00686     // case where DODAG already exists. This would always be a problem if
00687     // we'd heard adverts in between delete and create, but would be an instant
00688     // problem without this delete. Need to fix.
00689     rpl_delete_dodag(dodag);
00690 }
00691 
00692 /* Convert RPL configuration to generic trickle parameters. Returns true if
00693  * the value in the generic object has changed.
00694  */
00695 static bool rpl_dodag_conf_convert_trickle_parameters(trickle_params_t *params_out, const rpl_dodag_conf_t *conf)
00696 {
00697     /* Convert trickle parameters into 100ms ticks */
00698     uint32_t Imin_ms = conf->dio_interval_min < 32 ? (1ul << conf->dio_interval_min) : 0xfffffffful;
00699     uint32_t Imin_ticks = (Imin_ms + 99) / 100;
00700     uint32_t Imax_ms = (conf->dio_interval_min + conf->dio_interval_doublings) < 32 ?
00701                        (1ul << (conf->dio_interval_min + conf->dio_interval_doublings)) : 0xfffffffful;
00702     uint32_t Imax_ticks = (Imax_ms + 99) / 100;
00703     trickle_time_t Imin = (trickle_time_t)(Imin_ticks <= TRICKLE_TIME_MAX ?  Imin_ticks : TRICKLE_TIME_MAX);
00704     trickle_time_t Imax = (trickle_time_t)(Imax_ticks <= TRICKLE_TIME_MAX ?  Imax_ticks : TRICKLE_TIME_MAX);
00705     uint8_t k = conf->dio_redundancy_constant;
00706     if (params_out->Imin != Imin || params_out->Imax != Imax || params_out->k != k) {
00707         params_out->Imin = Imin;
00708         params_out->Imax = Imax;
00709         params_out->k = k;
00710         params_out->TimerExpirations = TRICKLE_EXPIRATIONS_INFINITE;
00711         return true;
00712     } else {
00713         return false;
00714     }
00715 }
00716 
00717 uint8_t rpl_dodag_mop(const rpl_dodag_t *dodag)
00718 {
00719     return dodag->g_mop_prf & RPL_MODE_MASK;
00720 }
00721 
00722 bool rpl_dodag_update_config(rpl_dodag_t *dodag, const rpl_dodag_conf_t *conf, const uint8_t *src, bool *become_leaf)
00723 {
00724     /* If already have config, don't update unless it's coming from preferred parent */
00725     if (dodag->have_config) {
00726         rpl_neighbour_t *parent = rpl_instance_preferred_parent(dodag->instance);
00727         if (parent && src && !addr_ipv6_equal(src, parent->ll_address)) {
00728             return true;
00729         }
00730     }
00731     dodag->config = *conf;
00732     bool restart_timer = rpl_dodag_conf_convert_trickle_parameters(&dodag->dio_timer_params, conf);
00733     dodag->have_config = true;
00734     if (restart_timer && rpl_instance_current_dodag(dodag->instance) == dodag) {
00735         /* They've changed the timing parameters for our currently-in-use trickle timer! */
00736         tr_warn("Trickle parameters changed");
00737         trickle_start(&dodag->instance->dio_timer, &dodag->dio_timer_params);
00738         dodag->new_config_advertisment_count = 0;
00739     }
00740     dodag->instance->of = rpl_objective_lookup(conf->objective_code_point);
00741     /* We could be a leaf of an unknown OCP. Still need an OF to choose parents */
00742     if (!dodag->instance->of) {
00743         dodag->instance->of = rpl_objective_lookup(RPL_OCP_OF0);
00744         if (!dodag->instance->of) {
00745             return false;
00746         }
00747         if (become_leaf) {
00748             *become_leaf = true;
00749         }
00750     }
00751     return true;
00752 }
00753 
00754 /* If we're currently a member of this DODAG, kick the DIO timers */
00755 void rpl_dodag_inconsistency(rpl_dodag_t *dodag)
00756 {
00757     if (rpl_instance_current_dodag(dodag->instance) == dodag) {
00758         trickle_inconsistent_heard(&dodag->instance->dio_timer, &dodag->dio_timer_params);
00759     }
00760 }
00761 
00762 void rpl_dodag_increment_dtsn(rpl_dodag_t *dodag)
00763 {
00764     if (rpl_instance_current_dodag(dodag->instance) == dodag) {
00765         rpl_instance_increment_dtsn(dodag->instance);
00766     }
00767 }
00768 
00769 void rpl_dodag_set_pref(rpl_dodag_t *dodag, uint8_t pref)
00770 {
00771     dodag->g_mop_prf &= ~RPL_DODAG_PREF_MASK;
00772     dodag->g_mop_prf |= pref;
00773 }
00774 
00775 rpl_cmp_t rpl_dodag_pref_compare(const rpl_dodag_t *a, const rpl_dodag_t *b)
00776 {
00777     uint8_t pref_a, pref_b;
00778     pref_a = a->g_mop_prf & RPL_DODAG_PREF_MASK;
00779     pref_b = b->g_mop_prf & RPL_DODAG_PREF_MASK;
00780     if (pref_a == pref_b) {
00781         return RPL_CMP_EQUAL;
00782     } else if (pref_a < pref_b) {
00783         return RPL_CMP_LESS;
00784     } else {
00785         return RPL_CMP_GREATER;
00786     }
00787 }
00788 
00789 void rpl_dodag_set_root(rpl_dodag_t *dodag, bool root)
00790 {
00791     if (root != dodag->root) {
00792         dodag->root = root;
00793         if (root) {
00794             rpl_instance_remove_parents(dodag->instance);
00795         } else {
00796             rpl_instance_run_parent_selection(dodag->instance);
00797         }
00798     }
00799 }
00800 
00801 #ifdef HAVE_RPL_ROOT
00802 bool rpl_dodag_am_root(const rpl_dodag_t *dodag)
00803 {
00804     return dodag->root;
00805 }
00806 #endif
00807 
00808 void rpl_dodag_set_leaf(rpl_dodag_t *dodag, bool leaf)
00809 {
00810     dodag->leaf = leaf;
00811 }
00812 
00813 bool rpl_dodag_am_leaf(const rpl_dodag_t *dodag)
00814 {
00815     return dodag->leaf || dodag->instance->domain->force_leaf;
00816 }
00817 
00818 bool rpl_dodag_is_current(const rpl_dodag_t *dodag)
00819 {
00820     return dodag->instance->current_dodag_version && dodag->instance->current_dodag_version->dodag == dodag;
00821 }
00822 
00823 const rpl_dodag_conf_t *rpl_dodag_get_config(const rpl_dodag_t *dodag)
00824 {
00825     return dodag->have_config ? &dodag->config : NULL;
00826 }
00827 
00828 uint8_t rpl_dodag_get_version_number_as_root(const rpl_dodag_t *dodag)
00829 {
00830     return dodag->instance->current_dodag_version->number;
00831 }
00832 
00833 void rpl_dodag_set_version_number_as_root(rpl_dodag_t *dodag, uint8_t number)
00834 {
00835     /* As root, unlike other nodes, we don't need to worry about maintaining
00836      * multiple rpl_dodag_version_t to track neighbours in each version and
00837      * our ranks in each version. We'll just quietly change the version number
00838      * of our only, always-current version.
00839      */
00840     rpl_dodag_version_t *version = dodag->instance->current_dodag_version;
00841     version->number = number;
00842     rpl_dodag_inconsistency(dodag);
00843 #if defined FEA_TRACE_SUPPORT && defined EXTRA_CONSISTENCY_CHECKS
00844     /* Sanity check that the above assertion is true - as root we shouldn't have
00845      * any neighbours referring to this version.
00846      */
00847     ns_list_foreach(rpl_neighbour_t, n, &dodag->instance->candidate_neighbours) {
00848         if (n->dodag_version == version) {
00849             tr_err("Root DODAG version had neighbour");
00850             break;
00851         }
00852     }
00853 #endif
00854     protocol_stats_update(STATS_RPL_GLOBAL_REPAIR, 1);
00855 }
00856 
00857 static bool rpl_dodag_in_use(const rpl_dodag_t *dodag)
00858 {
00859     if (dodag->root) {
00860         return true;
00861     }
00862 
00863     if (!dodag->have_config) {
00864         return false;
00865     }
00866 
00867     rpl_instance_t *instance = dodag->instance;
00868     ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
00869         if (neighbour->dodag_version->dodag == dodag) {
00870             return true;
00871         }
00872     }
00873 
00874     return false;
00875 }
00876 
00877 const rpl_dio_route_list_t *rpl_dodag_get_route_list(const rpl_dodag_t *dodag)
00878 {
00879     return &dodag->routes;
00880 }
00881 
00882 rpl_dio_route_t *rpl_dodag_update_dio_route(rpl_dodag_t *dodag, const uint8_t *prefix, uint8_t prefix_len, uint8_t flags, uint32_t lifetime, bool age)
00883 {
00884     rpl_dio_route_t *route = NULL;
00885     bool update = false;
00886 
00887     /* First look for matching prefix */
00888     ns_list_foreach(rpl_dio_route_t, r, &dodag->routes) {
00889         if (r->prefix_len == prefix_len && bitsequal(r->prefix, prefix, prefix_len)) {
00890             route = r;
00891             break;
00892         }
00893     }
00894 
00895     /* If not found, create a new one */
00896     if (!route) {
00897         uint_fast8_t prefix_bytes = (prefix_len + 7u) / 8u;
00898         route = rpl_alloc(sizeof(rpl_dio_route_t) + prefix_bytes);
00899         if (!route) {
00900             return NULL;
00901         }
00902 
00903         route->prefix_len = prefix_len;
00904         bitcopy0(route->prefix, prefix, prefix_len);
00905         ns_list_add_to_end(&dodag->routes, route);
00906         update = true;
00907     } else {
00908         if (lifetime != route->lifetime || route->flags != flags) {
00909             update = true;
00910         }
00911     }
00912 
00913     /* Update other info */
00914     route->lifetime = lifetime;
00915     route->hold_count = lifetime ? 0 : RPL_MAX_FINAL_RTR_ADVERTISEMENTS;
00916     route->flags = flags;
00917     route->age = age;
00918     if (update) {
00919         rpl_dodag_update_system_route(dodag, route);
00920     }
00921     return route;
00922 }
00923 
00924 void rpl_dodag_delete_dio_route(rpl_dodag_t *dodag, rpl_dio_route_t *route)
00925 {
00926     ns_list_remove(&dodag->routes, route);
00927     uint_fast8_t prefix_bytes = (route->prefix_len + 7u) / 8u;
00928     rpl_free(route, sizeof * route + prefix_bytes);
00929 }
00930 
00931 static void rpl_dodag_age_routes(rpl_dodag_t *dodag, uint16_t seconds)
00932 {
00933     ns_list_foreach_safe(rpl_dio_route_t, route, &dodag->routes) {
00934         if (route->age && route->lifetime != 0xFFFFFFFF) {
00935             if (route->lifetime > seconds) {
00936                 route->lifetime -= seconds;
00937             } else {
00938                 route->lifetime = 0;
00939                 if (route->hold_count == 0) {
00940                     rpl_dodag_delete_dio_route(dodag, route);
00941                 }
00942             }
00943         }
00944     }
00945 }
00946 
00947 const prefix_list_t *rpl_dodag_get_prefix_list(const rpl_dodag_t *dodag)
00948 {
00949     return &dodag->prefixes;
00950 }
00951 
00952 /* Called before updating all prefixes in a DIO */
00953 void rpl_dodag_update_unpublished_dio_prefix_start(rpl_dodag_t *dodag)
00954 {
00955     /* Clear age flags - will use as a marker for entries being in the DIO */
00956     ns_list_foreach(prefix_entry_t, entry, &dodag->prefixes) {
00957         if (!(entry->options & RPL_PIO_PUBLISHED)) {
00958             entry->options &= ~RPL_PIO_AGE;
00959         }
00960     }
00961 }
00962 
00963 
00964 /* Called after updating all prefixes in a DIO */
00965 void rpl_dodag_update_unpublished_dio_prefix_finish(rpl_dodag_t *dodag)
00966 {
00967     /* Any remaining non-published entries that don't have the age flag
00968      * set are not being sent by parent any more, so we should stop sending
00969      * too, except for the minimimum count requirement on 0 lifetime.
00970      */
00971     ns_list_foreach_safe(prefix_entry_t, entry, &dodag->prefixes) {
00972         if ((entry->options & (RPL_PIO_PUBLISHED | RPL_PIO_AGE | RPL_PIO_HOLD_MASK)) == 0) {
00973             rpl_dodag_delete_dio_prefix(dodag, entry);
00974         }
00975     }
00976 }
00977 
00978 prefix_entry_t *rpl_dodag_update_dio_prefix(rpl_dodag_t *dodag, const uint8_t *prefix, uint8_t prefix_len, uint8_t flags, uint32_t lifetime, uint32_t preftime, bool publish, bool age)
00979 {
00980     /* Don't let them set funny flags - we won't propagate them either.
00981      * Is not propagating them sensible? RFC isn't clear. Anyway, we use
00982      * the spare 5 flag bits internally...
00983      */
00984     flags &= (PIO_R | PIO_A | PIO_L);
00985 
00986     if (publish) {
00987         flags |= RPL_PIO_PUBLISHED;
00988     }
00989 
00990     if (age) {
00991         flags |= RPL_PIO_AGE;
00992     }
00993 
00994     prefix_entry_t *entry = icmpv6_prefix_add(&dodag->prefixes, prefix, prefix_len, lifetime, preftime, 0xff);
00995     /* icmpv6_prefix_add indicates a new entry by leaving options set to 0xFF */
00996     if (entry) {
00997         /* Newly-seen zero lifetimes should be advertised at least a few times -
00998          * count this down in the RPL_PIO_HOLD_COUNT field
00999          */
01000         if (lifetime == 0 && (entry->options == 0xFF || entry->lifetime != 0)) {
01001             flags |= RPL_MAX_FINAL_RTR_ADVERTISEMENTS;
01002         }
01003         entry->options = flags;
01004         entry->lifetime = lifetime;
01005         entry->preftime = preftime;
01006     }
01007     return entry;
01008 }
01009 
01010 void rpl_dodag_delete_dio_prefix(rpl_dodag_t *dodag, prefix_entry_t *prefix)
01011 {
01012     rpl_instance_t *instance = dodag->instance;
01013 
01014     if (instance && instance->domain->prefix_cb) {
01015         instance->domain->prefix_cb(prefix, instance->domain->cb_handle, NULL);
01016     }
01017 
01018     ns_list_remove(&dodag->prefixes, prefix);
01019     ns_dyn_mem_free(prefix);
01020 }
01021 
01022 static void rpl_dodag_age_prefixes(rpl_dodag_t *dodag, uint16_t seconds)
01023 {
01024     ns_list_foreach_safe(prefix_entry_t, prefix, &dodag->prefixes) {
01025         if (!(prefix->options & RPL_PIO_AGE)) {
01026             continue;
01027         }
01028         if (prefix->preftime != 0xFFFFFFFF) {
01029             if (prefix->preftime > seconds) {
01030                 prefix->preftime -= seconds;
01031             } else {
01032                 prefix->preftime = 0;
01033             }
01034         }
01035         if (prefix->lifetime != 0xFFFFFFFF) {
01036             if (prefix->lifetime > seconds) {
01037                 prefix->lifetime -= seconds;
01038             } else {
01039                 prefix->lifetime = 0;
01040                 /* Only delete on timeout if we're publishing - otherwise we will
01041                  * keep advertising until we see our parent stop advertising it - deletion
01042                  * is handled in rpl_control_process_prefix_options.
01043                  */
01044                 if ((prefix->options & (RPL_PIO_PUBLISHED | RPL_PIO_HOLD_MASK)) == RPL_PIO_PUBLISHED) {
01045                     rpl_dodag_delete_dio_prefix(dodag, prefix);
01046                 }
01047             }
01048         }
01049     }
01050 }
01051 
01052 static void rpl_dodag_slow_timer(rpl_dodag_t *dodag, uint16_t seconds)
01053 {
01054     rpl_dodag_age_routes(dodag, seconds);
01055     rpl_dodag_age_prefixes(dodag, seconds);
01056 }
01057 
01058 
01059 /* Look up a RPL instance by identifier. If the ID is local, addr must
01060  * identify the root - eg by providing either the source destination address of
01061  * a packet (depending on the 'O' flag).
01062  */
01063 rpl_instance_t *rpl_lookup_instance(const rpl_domain_t *domain, uint8_t instance_id, const uint8_t *addr)
01064 {
01065     if (rpl_instance_id_is_local(instance_id)) {
01066         instance_id &= ~RPL_INSTANCE_DEST;
01067     }
01068 
01069     ns_list_foreach(rpl_instance_t, instance, &domain->instances) {
01070         /* First match the instance ID */
01071         if (instance->id != instance_id) {
01072             continue;
01073         }
01074         /* If it's a global ID, this is a match */
01075         if (rpl_instance_id_is_global(instance_id)) {
01076             return instance;
01077         }
01078         /* If it's a local ID, address must match */
01079         const rpl_dodag_t *dodag = ns_list_get_first(&instance->dodags);
01080         if (addr && dodag && addr_ipv6_equal(dodag->id, addr)) {
01081             return instance;
01082         }
01083     }
01084     return NULL;
01085 }
01086 
01087 rpl_instance_t *rpl_create_instance(rpl_domain_t *domain, uint8_t instance_id)
01088 {
01089     rpl_instance_t *instance = rpl_alloc(sizeof(rpl_instance_t));
01090     if (!instance) {
01091         return NULL;
01092     }
01093     memset(instance, 0, sizeof(rpl_instance_t));
01094     ns_list_init(&instance->dodags);
01095     ns_list_init(&instance->candidate_neighbours);
01096     ns_list_init(&instance->dao_targets);
01097     instance->dtsn = rpl_seq_init();
01098     instance->last_dao_trigger_time = protocol_core_monotonic_time;
01099     instance->dao_sequence = rpl_seq_init();
01100     instance->id = instance_id;
01101     instance->domain = domain;
01102 
01103     ns_list_add_to_start(&domain->instances, instance);
01104     return instance;
01105 }
01106 
01107 void rpl_delete_instance(rpl_instance_t *instance)
01108 {
01109     rpl_domain_t *domain = instance->domain;
01110     ns_list_foreach_safe(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01111         rpl_delete_neighbour(instance, neighbour);
01112     }
01113     ns_list_foreach_safe(rpl_dodag_t, dodag, &instance->dodags) {
01114         rpl_delete_dodag(dodag);
01115     }
01116     ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) {
01117         rpl_delete_dao_target(instance, target);
01118     }
01119     ns_list_remove(&domain->instances, instance);
01120     rpl_free(instance, sizeof * instance);
01121 }
01122 
01123 /* Don't purge a DODAG we've used unless it's been gone for 15 minutes */
01124 #define DODAG_MIN_PURGE_AGE (15*60*10) // 15 minutes
01125 
01126 /* Choose worst DODAG in an instance - will be purgeable */
01127 static rpl_dodag_t *rpl_instance_choose_dodag_to_purge(const rpl_instance_t *instance)
01128 {
01129     rpl_dodag_t *worst = NULL;
01130 
01131     ns_list_foreach_reverse(rpl_dodag_t, dodag, &instance->dodags) {
01132         uint32_t dodag_age = protocol_core_monotonic_time - dodag->timestamp;
01133         if (rpl_dodag_in_use(dodag)) {
01134             continue;
01135         }
01136 
01137         if (dodag_age < DODAG_MIN_PURGE_AGE && dodag->used) {
01138             continue;
01139         }
01140 
01141         if (!worst) {
01142             goto new_worst;
01143         }
01144 
01145         /* Prefer to purge least-recently-heard-from */
01146         uint32_t worst_age = protocol_core_monotonic_time - worst->timestamp;
01147         if (dodag_age <= worst_age) {
01148             continue;
01149         } else {
01150             goto new_worst;
01151         }
01152 
01153 new_worst:
01154         worst = dodag;
01155         worst_age = dodag_age;
01156     }
01157 
01158     return worst;
01159 }
01160 
01161 /* Choose worst neighbour in an instance - may be a candidate for purging */
01162 static rpl_neighbour_t *rpl_instance_choose_worst_neighbour(const rpl_instance_t *instance)
01163 {
01164     rpl_neighbour_t *worst = NULL;
01165     bool worst_acceptable = false;
01166 
01167     /* Parents will be first - loop backwards so we take non-parents first */
01168     ns_list_foreach_reverse(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01169         bool acceptable = instance->of->neighbour_acceptable(instance, neighbour);
01170         if (!worst) {
01171             goto new_worst;
01172         }
01173 
01174         /* Stop if crossing from non-parents to parents - parents can't be worse */
01175         if (neighbour->dodag_parent && !worst->dodag_parent) {
01176             break;
01177         }
01178 
01179         /* Prefer to purge "unacceptable" neighbours according to OF */
01180         if (acceptable && !worst_acceptable) {
01181             continue;
01182         } else if (!acceptable && worst_acceptable) {
01183             goto new_worst;
01184         }
01185 
01186         /* Prefer to purge least-recently-heard-from */
01187         uint32_t neighbour_age = protocol_core_monotonic_time - neighbour->dio_timestamp;
01188         uint32_t worst_age = protocol_core_monotonic_time - worst->dio_timestamp;
01189         if (neighbour_age <= worst_age) {
01190             continue;
01191         } else {
01192             goto new_worst;
01193         }
01194 
01195 new_worst:
01196         worst = neighbour;
01197         worst_acceptable = acceptable;
01198     }
01199 
01200     return worst;
01201 }
01202 
01203 /* Purge one item from an instance */
01204 bool rpl_instance_purge(rpl_instance_t *instance)
01205 {
01206     /* Purge this instance itself if no remaining neighbours or DODAGs
01207      * (time restrictions on those are sufficient - no need for extra)
01208      */
01209     if (ns_list_is_empty(&instance->candidate_neighbours) &&
01210             ns_list_is_empty(&instance->dodags)) {
01211         rpl_delete_instance(instance);
01212         return true;
01213     }
01214 
01215     /* May purge a DODAG if not used for some time, and no remaining neighbours */
01216     rpl_dodag_t *dodag = rpl_instance_choose_dodag_to_purge(instance);
01217     if (dodag) {
01218         rpl_delete_dodag(dodag);
01219         return true;
01220     }
01221 
01222     /* Otherwise, delete a non-parent neighbour we've considered at least once.
01223      * (We don't want to delete a new neighbour before it gets a chance to
01224      * become a new parent)
01225      */
01226     rpl_neighbour_t *neighbour = rpl_instance_choose_worst_neighbour(instance);
01227     if (neighbour && neighbour->considered && !neighbour->dodag_parent && neighbour->dao_path_control == 0) {
01228         rpl_delete_neighbour(instance, neighbour);
01229         return true;
01230     }
01231     return false;
01232 }
01233 
01234 void rpl_instance_neighbours_changed(rpl_instance_t *instance, const rpl_dodag_t *dodag)
01235 {
01236     instance->neighbours_changed = true;
01237     uint16_t delay = rpl_policy_dio_parent_selection_delay(instance->domain);
01238     if (dodag) {
01239         //Convert imin 100ms tick to seconds
01240         uint16_t i_min_delay = dodag->dio_timer_params.Imin / 10;
01241         if (i_min_delay > delay) {
01242             delay = i_min_delay;
01243         }
01244     }
01245     rpl_instance_trigger_parent_selection(instance, delay);
01246 }
01247 
01248 static void rpl_instance_remove_parents(rpl_instance_t *instance)
01249 {
01250     ns_list_foreach(rpl_neighbour_t, n, &instance->candidate_neighbours) {
01251         n->dodag_parent = false;
01252     }
01253 }
01254 
01255 /* Convert RPL lifetime (8-bit in units) to core lifetime (32-bit seconds) */
01256 static uint32_t rpl_lifetime(uint8_t lifetime, uint16_t lifetime_unit)
01257 {
01258     return lifetime == 0xff ? 0xffffffff : lifetime * (uint32_t) lifetime_unit;
01259 }
01260 
01261 static uint32_t rpl_default_lifetime(rpl_dodag_t *dodag)
01262 {
01263     return rpl_lifetime(dodag->config.default_lifetime, dodag->config.lifetime_unit);
01264 }
01265 
01266 /* Adjust a lifetime (in seconds) downwards to account for its age */
01267 static uint32_t rpl_aged_lifetime(uint32_t lifetime, uint32_t timestamp)
01268 {
01269     if (lifetime != 0xffffffff) {
01270         uint32_t age = (protocol_core_monotonic_time - timestamp) / 10;
01271         if (age < lifetime) {
01272             lifetime -= age;
01273         } else {
01274             lifetime = 0;
01275         }
01276     }
01277     return lifetime;
01278 }
01279 
01280 static void rpl_instance_update_system_dio_route(rpl_instance_t *instance, rpl_neighbour_t *parent, rpl_dio_route_t *route)
01281 {
01282     int8_t pref;
01283     switch (route->flags & RA_PRF_MASK) {
01284         case RA_PRF_LOW:
01285             pref = -1;
01286             break;
01287         case RA_PRF_MEDIUM:
01288             pref = 0;
01289             break;
01290         case RA_PRF_HIGH:
01291             pref = 1;
01292             break;
01293         default:
01294             return;
01295     }
01296 
01297     uint8_t metric = ipv6_route_pref_to_metric(pref) + parent->dodag_pref;
01298 
01299     ipv6_route_add_metric(route->prefix, route->prefix_len, parent->interface_id, parent->ll_address, ROUTE_RPL_DIO, parent, instance->id, route->lifetime, metric);
01300 }
01301 
01302 /* Called when a DIO has been received */
01303 void rpl_dodag_update_implicit_system_routes(rpl_dodag_t *dodag, rpl_neighbour_t *parent)
01304 {
01305     if (!rpl_dodag_is_current(dodag) || !parent->dodag_parent) {
01306         return;
01307     }
01308 
01309     uint32_t default_lifetime = rpl_default_lifetime(dodag);
01310     uint8_t metric = IPV6_ROUTE_DEFAULT_METRIC + parent->dodag_pref;
01311 
01312     /* Always add the "root" default route - only used for per-instance lookup */
01313     ipv6_route_add_metric(NULL, 0, parent->interface_id, parent->ll_address, ROUTE_RPL_INSTANCE, parent, dodag->instance->id, default_lifetime, metric);
01314 
01315     /* Also add a specific route to the DODAGID */
01316     ipv6_route_add_metric(dodag->id, 128, parent->interface_id, parent->ll_address, ROUTE_RPL_ROOT, parent, dodag->instance->id, default_lifetime, metric);
01317 
01318 }
01319 
01320 /* Called when a DIO RIO route has been updated (but not the parent list) */
01321 static void rpl_dodag_update_system_route(rpl_dodag_t *dodag, rpl_dio_route_t *route)
01322 {
01323     if (!rpl_dodag_is_current(dodag)) {
01324         return;
01325     }
01326 
01327     rpl_instance_t *instance = dodag->instance;
01328 
01329     ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01330         if (neighbour->dodag_parent) {
01331             rpl_instance_update_system_dio_route(instance, neighbour, route);
01332         }
01333     }
01334 }
01335 
01336 /* Called when a parent has been added/updated (but not the DIO route list) */
01337 static void rpl_instance_update_system_routes_through_parent(rpl_instance_t *instance, rpl_neighbour_t *parent)
01338 {
01339     rpl_dodag_t *dodag = parent->dodag_version->dodag;
01340 
01341     rpl_dodag_update_implicit_system_routes(dodag, parent);
01342 
01343     /* Then add the specific routes listed in the DIO as ROUTE_RPL_DIO */
01344     ns_list_foreach(rpl_dio_route_t, route, &dodag->routes) {
01345         rpl_instance_update_system_dio_route(instance, parent, route);
01346     }
01347 }
01348 
01349 static void rpl_instance_remove_system_routes_through_parent(rpl_instance_t *instance, rpl_neighbour_t *parent)
01350 {
01351     (void)instance;
01352 
01353     ipv6_route_table_remove_info(parent->interface_id, ROUTE_RPL_INSTANCE, parent);
01354     ipv6_route_table_remove_info(parent->interface_id, ROUTE_RPL_DIO, parent);
01355     ipv6_route_table_remove_info(parent->interface_id, ROUTE_RPL_ROOT, parent);
01356 }
01357 
01358 static void trace_info_print(const char *fmt, ...)
01359 {
01360     va_list ap;
01361     va_start(ap, fmt);
01362     vtracef(TRACE_LEVEL_INFO, TRACE_GROUP, fmt, ap);
01363     va_end(ap);
01364 }
01365 
01366 static uint32_t rpl_dio_imax_time_calculate(uint16_t Imax, uint16_t fixed_point)
01367 {
01368     return (((uint32_t)Imax * fixed_point) / 0x0100);
01369 }
01370 
01371 
01372 void rpl_instance_run_parent_selection(rpl_instance_t *instance)
01373 {
01374     bool parent_set_change = false;
01375     rpl_dodag_version_t *original_version = instance->current_dodag_version;
01376     uint16_t original_rank = instance->current_rank;
01377 
01378     instance->parent_selection_timer = rpl_policy_parent_selection_period(instance->domain);
01379 
01380     if (!instance->of) {
01381         return;
01382     }
01383 
01384     if (instance->current_dodag_version && instance->current_dodag_version->dodag->root) {
01385         return;
01386     }
01387 
01388     ns_list_foreach_safe(rpl_neighbour_t, n, &instance->candidate_neighbours) {
01389         //Remove a Parent candidates which are not heared a long time ago and not slected ones
01390         if (!n->dodag_parent && (rpl_aged_lifetime(rpl_default_lifetime(n->dodag_version->dodag), n->dio_timestamp) == 0)) {
01391             rpl_delete_neighbour(instance, n);
01392             continue;
01393         }
01394         n->old_dao_path_control = n->dao_path_control;
01395         n->dao_path_control = 0;
01396         n->was_dodag_parent = n->dodag_parent;
01397         n->dodag_parent = false;
01398         n->considered = true;
01399     }
01400 
01401     rpl_neighbour_t *original_preferred = rpl_instance_preferred_parent(instance);
01402 
01403     instance->of->parent_selection(instance);
01404 
01405     ns_list_foreach(rpl_neighbour_t, n, &instance->candidate_neighbours) {
01406         if (n->was_dodag_parent != n->dodag_parent) {
01407             tr_info("%s parent %s", n->dodag_parent ? "Added" : "Removed", trace_ipv6(n->ll_address));
01408             parent_set_change = true;
01409             /* Remove routes through a deselected parent */
01410             if (!n->dodag_parent) {
01411                 rpl_instance_remove_system_routes_through_parent(instance, n);
01412             }
01413         }
01414         /* Always re-run route update (in case of changed preference values) */
01415         if (n->dodag_parent) {
01416             rpl_instance_update_system_routes_through_parent(instance, n);
01417         }
01418         n->was_dodag_parent = false;
01419     }
01420 
01421     rpl_neighbour_t *preferred_parent = rpl_instance_preferred_parent(instance);
01422 
01423     if (preferred_parent) {
01424         rpl_control_disable_ra_routes(instance->domain);
01425     } else {
01426         rpl_instance_poison(instance, rpl_policy_repair_poison_count(instance->domain));
01427     }
01428 
01429     if (original_preferred != preferred_parent) {
01430         protocol_stats_update(STATS_RPL_PARENT_CHANGE, 1);
01431         if (preferred_parent) {
01432             tr_debug("New preferred parent %s", trace_array(preferred_parent->ll_address, 16));
01433         }
01434     }
01435 
01436     // Sets new preferred parent
01437     if (preferred_parent) {
01438         ipv6_map_ip_to_ll_and_call_ll_addr_handler(NULL, preferred_parent->interface_id, NULL, preferred_parent->ll_address,
01439                                                    protocol_6lowpan_neighbor_priority_set);
01440         // Sets secondary parent
01441         rpl_neighbour_t *sec_parent = ns_list_get_next(&instance->candidate_neighbours, preferred_parent);
01442         if (sec_parent && sec_parent->dodag_parent) {
01443             ipv6_map_ip_to_ll_and_call_ll_addr_handler(NULL, sec_parent->interface_id, NULL, sec_parent->ll_address,
01444                                                        protocol_6lowpan_neighbor_second_priority_set);
01445         } else {
01446             protocol_6lowpan_neighbor_priority_clear_all(preferred_parent->interface_id, PRIORITY_2ND);
01447         }
01448     }
01449 
01450     //Control Local repair state
01451     if (preferred_parent) {
01452         // Always stop repair if we find a parent
01453         rpl_instance_set_local_repair(instance, false);
01454         //Validate time from last DIO
01455 
01456         uint32_t time_between_parent = protocol_core_monotonic_time - preferred_parent->dio_timestamp;
01457         uint32_t accepted_time = rpl_dio_imax_time_calculate(instance->current_dodag_version->dodag->dio_timer_params.Imax, rpl_policy_dio_validity_period(instance->domain));
01458 
01459         if (accepted_time < time_between_parent) {
01460             rpl_control_transmit_dis(instance->domain, NULL, RPL_SOLINFO_PRED_INSTANCEID, instance->id, NULL, 0, preferred_parent->ll_address);
01461         }
01462 
01463     } else if (original_preferred) {
01464         // Only start repair if we just lost a parent
01465         rpl_instance_set_local_repair(instance, true);
01466     } else {
01467         // !preferred_parent && !original_preferred - didn't have a parent,
01468         // still don't. Leave repair flag as-is (would be off on initial start
01469         // up, may be on if having problems mid-session).
01470     }
01471 
01472     if (rpl_instance_mop(instance) != RPL_MODE_NO_DOWNWARD) {
01473         rpl_downward_process_dao_parent_changes(instance);
01474     }
01475 
01476     /* Anyone who's not a parent can be pruned now (eg bad link cost) */
01477     ns_list_foreach_safe(rpl_neighbour_t, n, &instance->candidate_neighbours) {
01478         if (n->dodag_parent) {
01479             continue;
01480         }
01481         if (!instance->of->neighbour_acceptable(instance, n)) {
01482             rpl_delete_neighbour(instance, n);
01483         }
01484     }
01485     rpl_control_print(trace_info_print);
01486     /* Changing DODAG version is an inconsistency */
01487     if (original_version != instance->current_dodag_version) {
01488         //learn Routes an Prefixes
01489         if (preferred_parent && instance->current_dodag_version) {
01490             rpl_dodag_t *dodag = instance->current_dodag_version->dodag;
01491             protocol_interface_info_entry_t *rpl_interface = protocol_stack_interface_info_get_by_id(preferred_parent->interface_id);
01492             if (rpl_interface) {
01493                 ns_list_foreach(prefix_entry_t, prefix, &dodag->prefixes) {
01494                     rpl_control_process_prefix_option(prefix, rpl_interface);
01495                     if (instance->domain->prefix_cb) {
01496                         instance->domain->prefix_cb(prefix, rpl_interface, preferred_parent->ll_address);
01497                     }
01498                 }
01499             }
01500         }
01501 
01502         rpl_instance_inconsistency(instance);
01503         return;
01504     }
01505 
01506     /* Check for "consistent" indication as per RFC 6550 8.3 - if not
01507      * "consistent" by this definition, we reset Trickle consistency counter,
01508      * and do not process any more consistency events this interval.
01509      * See comments in rpl_control_dio_handler() for more info.
01510      */
01511     if (parent_set_change ||
01512             original_preferred != preferred_parent ||
01513             !(instance->current_dodag_version &&
01514               (rpl_rank_compare(instance->current_dodag_version->dodag, original_rank, instance->current_rank) & RPL_CMP_EQUAL))) {
01515         instance->dio_not_consistent = true;
01516         instance->dio_timer.c = 0;
01517     }
01518 }
01519 
01520 void rpl_instance_remove_interface(rpl_instance_t *instance, int8_t if_id)
01521 {
01522     ns_list_foreach_safe(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01523         if (neighbour->interface_id == if_id) {
01524             rpl_delete_neighbour(instance, neighbour);
01525         }
01526     }
01527 }
01528 
01529 /* Trigger DIO transmission - all interfaces multicast if addr+cur are NULL, else unicast */
01530 void rpl_instance_dio_trigger(rpl_instance_t *instance, protocol_interface_info_entry_t *cur, const uint8_t *addr)
01531 {
01532     uint16_t rank = instance->current_rank;
01533     rpl_dodag_version_t *dodag_version = instance->current_dodag_version;
01534     rpl_dodag_t *dodag;
01535     if (dodag_version) {
01536         dodag = dodag_version->dodag;
01537     } else if (instance->poison_count) {
01538         /* When poisoning, we can send using data from an arbitrary DODAG/version */
01539         dodag = ns_list_get_first(&instance->dodags);
01540         if (dodag) {
01541             dodag_version = ns_list_get_first(&dodag->versions);
01542         }
01543     } else {
01544         dodag = NULL;
01545     }
01546 
01547     if (!dodag || !dodag_version) {
01548         return;
01549     }
01550 
01551     if (instance->poison_count) {
01552         instance->poison_count--;
01553         rank = RPL_RANK_INFINITE;
01554         tr_debug("Poison count -> set RPL_RANK_INFINITE");
01555     }
01556 
01557     // Always send config in unicasts (as required), never in multicasts (optional)
01558     rpl_dodag_conf_t *conf;
01559     if (addr) {
01560         conf = &dodag->config;
01561     } else if (dodag->new_config_advertisment_count < rpl_policy_dio_multicast_config_advertisment_min_count()) {
01562         conf = &dodag->config;
01563         dodag->new_config_advertisment_count++;
01564     } else {
01565         conf = NULL;
01566     }
01567 
01568     rpl_control_transmit_dio(instance->domain, cur, instance->id, dodag_version->number, rank, dodag->g_mop_prf, instance->dtsn, dodag, dodag->id, conf, addr);
01569 
01570     dodag_version->last_advertised_rank = rank;
01571 
01572     /* When we advertise a new lowest rank, need to re-evaluate our rank limits */
01573     if (rank < dodag_version->lowest_advertised_rank) {
01574         dodag_version->lowest_advertised_rank = rank;
01575 #if 0
01576         // Standard RFC 6550 behaviour
01577         dodag_version->hard_rank_limit = rpl_rank_add(rank, dodag->config.dag_max_rank_increase);
01578 #else
01579         // Round up hard limit - DAGRank interpretation. Contrary to wording of RFC 6550 8.2.2.4.3,
01580         // but needed to cope reasonably with Wi-SUN insisting on DAGMaxRankIncrease of 0.
01581         // Interpret that as a request to not increase DAGRank, rather than Rank.
01582         //
01583         // Example, if DAGMaxRankIncrease is 0, MinHopRankIncrease is 0x80, and our advertised
01584         // 0xC0, then we permit up to 0xFF, which doesn't increase DAGRank. If DAGMaxRankIncrease
01585         // is 0x80, then we permit can go form 0xC0 to 0x17F, increasing DAGRank by 1, even though
01586         // it's a Rank increase of 0xBF. Fractional parts of DAGMaxRankIncrease are ignored.
01587         uint16_t dagrank = nrpl_dag_rank(dodag, rank);
01588         uint16_t dagmaxinc = nrpl_dag_rank(dodag, dodag->config.dag_max_rank_increase);
01589         uint16_t dagmax = rpl_rank_add(dagrank, dagmaxinc);
01590         if (dagmax == RPL_RANK_INFINITE) {
01591             dodag_version->hard_rank_limit = RPL_RANK_INFINITE;
01592         } else {
01593             dodag_version->hard_rank_limit = nrpl_rank(dodag, 1 + dagmax) - 1;
01594         }
01595 #endif
01596     }
01597     rpl_dodag_version_limit_greediness(dodag_version, rank);
01598 
01599     instance->last_advertised_dodag_version = dodag_version;
01600 }
01601 
01602 static void rpl_instance_dis_timer(rpl_instance_t *instance, uint16_t seconds)
01603 {
01604     if (instance->repair_dis_timer > seconds) {
01605         instance->repair_dis_timer -= seconds;
01606     } else if (instance->repair_dis_timer != 0) {
01607         tr_debug("Timed repair DIS %d", instance->id);
01608         instance->repair_dis_timer = 0;
01609         instance->repair_dis_count++;
01610         rpl_control_transmit_dis(instance->domain, NULL, RPL_SOLINFO_PRED_INSTANCEID, instance->id, NULL, 0, NULL);
01611         if (instance->repair_dis_count < rpl_policy_repair_dis_count(instance->domain)) {
01612             uint16_t t = rpl_policy_repair_initial_dis_delay(instance->domain);
01613             uint16_t max = rpl_policy_repair_maximum_dis_interval(instance->domain);
01614             for (uint_fast8_t n = instance->repair_dis_count; n; n--) {
01615                 if (t < 0x8000 && t < max) {
01616                     t <<= 1;
01617                 } else {
01618                     t = max;
01619                     break;
01620                 }
01621             }
01622             if (t > max) {
01623                 t = max;
01624             }
01625             instance->repair_dis_timer = t;
01626         } else {
01627             rpl_control_event(instance->domain, RPL_EVENT_LOCAL_REPAIR_NO_MORE_DIS);
01628         }
01629     }
01630 }
01631 
01632 void rpl_instance_set_local_repair(rpl_instance_t *instance, bool repair)
01633 {
01634     if (instance->local_repair == repair) {
01635         return;
01636     }
01637 
01638     instance->local_repair = repair;
01639 
01640     if (repair) {
01641         /* Notify RPL user to state switch */
01642         rpl_control_event(instance->domain, RPL_EVENT_LOCAL_REPAIR_START);
01643         protocol_stats_update(STATS_RPL_LOCAL_REPAIR, 1);
01644         instance->repair_dis_timer = rpl_policy_repair_initial_dis_delay(instance->domain);
01645         instance->repair_dis_count = 0;
01646     } else {
01647         instance->repair_dis_timer = 0;
01648     }
01649 
01650     /* When repair ends, eliminate all higher-rank neighbours (potential sub-DODAG) from table */
01651     if (!repair && instance->current_dodag_version) {
01652         ns_list_foreach_safe(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01653             if (rpl_dodag_version_rank_indicates_possible_sub_dodag(neighbour->dodag_version, neighbour->rank)) {
01654                 rpl_delete_neighbour(instance, neighbour);
01655             }
01656         }
01657     }
01658 }
01659 
01660 bool rpl_instance_local_repair(const rpl_instance_t *instance)
01661 {
01662     return instance->local_repair;
01663 }
01664 
01665 uint16_t rpl_instance_current_rank(const rpl_instance_t *instance)
01666 {
01667     return instance->current_rank;
01668 }
01669 
01670 bool rpl_instance_address_is_parent(rpl_instance_t *instance, const uint8_t *ipv6_addr)
01671 {
01672     ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01673         if (!neighbour->dodag_parent) {
01674             // list is ordered so first encounter of false means no more parents in list
01675             return false;
01676         }
01677 
01678         if (addr_ipv6_equal(neighbour->ll_address, ipv6_addr)) {
01679             return true;
01680         }
01681     }
01682     return false;
01683 }
01684 
01685 bool rpl_instance_address_is_candidate(rpl_instance_t *instance, const uint8_t *ipv6_addr, uint16_t candidate_amount)
01686 {
01687     uint16_t list_compared = 0;
01688 
01689     ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01690         if (addr_ipv6_equal(neighbour->ll_address, ipv6_addr)) {
01691             return true;
01692         }
01693         list_compared++;
01694         if (candidate_amount && list_compared >= candidate_amount) {
01695             return false;
01696         }
01697 
01698     }
01699     return false;
01700 }
01701 
01702 uint16_t rpl_instance_address_candidate_count(rpl_instance_t *instance, bool selected_parents)
01703 {
01704     uint16_t parent_list = 0;
01705 
01706     ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01707 
01708 
01709         if (selected_parents) {
01710             if (neighbour->dodag_parent) {
01711                 parent_list++;
01712             }
01713         } else {
01714             parent_list++;
01715         }
01716     }
01717     return parent_list;
01718 }
01719 
01720 
01721 void rpl_instance_neighbor_delete(rpl_instance_t *instance, const uint8_t *ipv6_addr)
01722 {
01723     ns_list_foreach_safe(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) {
01724         if (addr_ipv6_equal(neighbour->ll_address, ipv6_addr)) {
01725             rpl_delete_neighbour(instance, neighbour);
01726         }
01727     }
01728     return;
01729 }
01730 
01731 void rpl_instance_slow_timer(rpl_instance_t *instance, uint16_t seconds)
01732 {
01733     ns_list_foreach(rpl_dodag_t, dodag, &instance->dodags) {
01734         rpl_dodag_slow_timer(dodag, seconds);
01735     }
01736 
01737     rpl_instance_parent_address_reg_timer_update(instance, seconds);
01738     rpl_instance_parent_selection_timer(instance, seconds);
01739     if (!rpl_instance_preferred_parent(instance)) {
01740         protocol_stats_update(STATS_RPL_TIME_NO_NEXT_HOP, 1);
01741         rpl_instance_dis_timer(instance, seconds);
01742     }
01743 }
01744 
01745 
01746 void rpl_upward_dio_timer(rpl_instance_t *instance, uint16_t ticks)
01747 {
01748     rpl_dodag_version_t *dodag_version = instance->current_dodag_version;
01749     rpl_dodag_t *dodag;
01750     if (dodag_version) {
01751         dodag = dodag_version->dodag;
01752     } else if (instance->poison_count) {
01753         /* When poisoning, we can send using data from an arbitrary DODAG/version */
01754         dodag = ns_list_get_first(&instance->dodags);
01755         if (dodag) {
01756             dodag_version = ns_list_get_first(&dodag->versions);
01757         }
01758     } else {
01759         dodag = NULL;
01760     }
01761 
01762     if (!dodag || !dodag_version) {
01763         return;
01764     }
01765 
01766     /* Leaves don't send normal periodic DIOs */
01767     if (rpl_dodag_am_leaf(dodag) && !instance->poison_count) {
01768         return;
01769     }
01770     // We dont have any valid address in interface
01771     if (ns_list_count(&instance->dao_targets) == 0) {
01772         return;
01773     }
01774     /* Address registrations for parent ongoing*/
01775     if (rpl_policy_parent_confirmation_requested() && instance->pending_neighbour_confirmation) {
01776         return;
01777     }
01778     /* If we are waiting for DAO or DAO registration is needed we dont send periodic DIOs */
01779     if (instance->dao_in_transit || instance->delay_dao_timer > 0) {
01780         return;
01781     }
01782     if (trickle_timer(&instance->dio_timer, &dodag->dio_timer_params, ticks)) {
01783         instance->dio_not_consistent = false;
01784         rpl_instance_dio_trigger(instance, NULL, NULL);
01785     }
01786 }
01787 
01788 void rpl_upward_print_neighbour(const rpl_neighbour_t *neighbour, route_print_fn_t *print_fn)
01789 {
01790     uint16_t path_cost;
01791     if (neighbour->dodag_version->dodag->instance->of) {
01792         path_cost = neighbour->dodag_version->dodag->instance->of->path_cost(neighbour);
01793     } else {
01794         path_cost = 0xFFFF;
01795     }
01796 
01797     ROUTE_PRINT_ADDR_STR_BUFFER_INIT(addr_str_ll);
01798     ROUTE_PRINT_ADDR_STR_BUFFER_INIT(addr_str_global);
01799     print_fn("   %2.0d%c%04x %04x %02x %s%%%d (%s)",
01800              neighbour->dodag_parent ? neighbour->dodag_pref + 1 : 0,
01801              neighbour->dodag_version && rpl_instance_preferred_parent(neighbour->dodag_version->dodag->instance) == neighbour ? '*' : ' ',
01802              neighbour->rank,
01803              path_cost,
01804              neighbour->dao_path_control,
01805              ROUTE_PRINT_ADDR_STR_FORMAT(addr_str_ll, neighbour->ll_address), neighbour->interface_id,
01806              ROUTE_PRINT_ADDR_STR_FORMAT(addr_str_global, neighbour->global_address));
01807 }
01808 
01809 void rpl_upward_print_neighbours_in_version(const rpl_neighbour_list_t *list, const rpl_dodag_version_t *version, route_print_fn_t *print_fn)
01810 {
01811     ns_list_foreach(rpl_neighbour_t, neighbour, list) {
01812         if (neighbour->dodag_version == version) {
01813             rpl_upward_print_neighbour(neighbour, print_fn);
01814         }
01815     }
01816 }
01817 
01818 void rpl_upward_print_dodag(rpl_instance_t *instance, rpl_dodag_t *dodag, route_print_fn_t *print_fn)
01819 {
01820     /* Summary */
01821     ROUTE_PRINT_ADDR_STR_BUFFER_INIT(addr_str);
01822     print_fn("DODAG %s", ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, dodag->id));
01823     print_fn("  G=%d MOP=%d Prf=%d", dodag->g_mop_prf & RPL_GROUNDED ? 1 : 0,
01824              (dodag->g_mop_prf & RPL_MODE_MASK) >> RPL_MODE_SHIFT,
01825              (dodag->g_mop_prf & RPL_DODAG_PREF_MASK));
01826     /* Routes */
01827     ns_list_foreach(rpl_dio_route_t, route, &dodag->routes) {
01828         uint8_t addr[16] = { 0 } ;
01829         int_fast8_t pref;
01830         switch (route->flags & RA_PRF_MASK) {
01831             case RA_PRF_LOW:
01832                 pref = -1;
01833                 break;
01834             case RA_PRF_MEDIUM:
01835                 pref = 0;
01836                 break;
01837             case RA_PRF_HIGH:
01838                 pref = 1;
01839                 break;
01840             default:
01841                 pref = 2;
01842                 break;
01843         }
01844         bitcopy(addr, route->prefix, route->prefix_len);
01845         if (route->lifetime == 0xFFFFFFFF) {
01846             print_fn("%24s/%-3u lifetime:infinite pref:%"PRIdFAST8,
01847                      ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, addr), route->prefix_len, pref);
01848 
01849         } else {
01850             print_fn("%24s/%-3u lifetime:%"PRIu32" pref:%"PRIdFAST8,
01851                      ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, addr), route->prefix_len, route->lifetime, pref);
01852         }
01853     }
01854     /* Prefixes */
01855     ns_list_foreach(prefix_entry_t, prefix, &dodag->prefixes) {
01856         uint8_t addr[16] = { 0 } ;
01857         bitcopy(addr, prefix->prefix, prefix->prefix_len);
01858         if (prefix->lifetime == 0xFFFFFFFF) {
01859             print_fn("%24s/%-3u lifetime:infinite flags:%c%c%c",
01860                      ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, addr), prefix->prefix_len,
01861                      prefix->options & PIO_L ? 'L' : '-',
01862                      prefix->options & PIO_A ? 'A' : '-',
01863                      prefix->options & RPL_PIO_PUBLISHED ? '*' : ' '
01864                     );
01865         } else {
01866             print_fn("%24s/%-3u lifetime:%"PRIu32" flags:%c%c%c",
01867                      ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, addr), prefix->prefix_len, prefix->lifetime,
01868                      prefix->options & PIO_L ? 'L' : '-',
01869                      prefix->options & PIO_A ? 'A' : '-',
01870                      prefix->options & RPL_PIO_PUBLISHED ? '*' : ' '
01871                     );
01872         }
01873     }
01874     /* Versions */
01875     ns_list_foreach(rpl_dodag_version_t, version, &dodag->versions) {
01876         print_fn("  Version %d", version->number);
01877         if (version == instance->current_dodag_version) {
01878             print_fn("  *Current version* Rank=%04x", instance->current_rank);
01879         }
01880         rpl_upward_print_neighbours_in_version(&instance->candidate_neighbours, version, print_fn);
01881     }
01882 }
01883 
01884 void rpl_upward_print_instance(rpl_instance_t *instance, route_print_fn_t *print_fn)
01885 {
01886     print_fn("RPL Instance %d", instance->id);
01887     print_fn("---------------");
01888     ns_list_foreach(rpl_dodag_t, dodag, &instance->dodags) {
01889         rpl_upward_print_dodag(instance, dodag, print_fn);
01890     }
01891     if (instance->current_dodag_version) {
01892         const trickle_params_t *params = &instance->current_dodag_version->dodag->dio_timer_params;
01893         const trickle_t *timer = &instance->dio_timer;
01894 
01895         print_fn("DIO trickle Imin=%d, Imax=%d, k=%d", params->Imin, params->Imax, params->k);
01896         print_fn("            I=%d, now=%d, t=%d, c=%d", timer->I, timer->now, timer->t, timer->c);
01897     }
01898 }
01899 
01900 uint16_t rpl_upward_read_dao_target_list_size(const rpl_instance_t *instance, const uint8_t *target_prefix)
01901 {
01902 
01903     if (target_prefix) {
01904         uint16_t registered_address_count = 0;
01905         ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) {
01906             if (bitsequal(target->prefix, target_prefix, 64)) {
01907                 registered_address_count++;
01908             }
01909         }
01910         return registered_address_count;
01911     }
01912 
01913     return ns_list_count(&instance->dao_targets);
01914 }
01915 
01916 /* Backwards-compatibility implementation of net_rpl.h API designed for old implementation */
01917 bool rpl_upward_read_dodag_info(const rpl_instance_t *instance, rpl_dodag_info_t *dodag_info)
01918 {
01919     rpl_dodag_version_t *version = rpl_instance_current_dodag_version(instance);
01920     if (!version) {
01921         return false;
01922     }
01923 
01924     rpl_dodag_t *dodag = version->dodag;
01925 
01926     memcpy(dodag_info->dodag_id, dodag->id, 16);
01927     dodag_info->instance_id = instance->id;
01928     dodag_info->flags = dodag->g_mop_prf;
01929     dodag_info->version_num = version->number;
01930     dodag_info->DTSN = instance->dtsn;
01931     dodag_info->curent_rank = instance->current_rank;
01932     dodag_info->parent_flags = 0;
01933     dodag_info->dag_min_hop_rank_inc = dodag->config.min_hop_rank_increase;
01934 
01935     rpl_neighbour_t *pref_parent = rpl_instance_preferred_parent(instance);
01936     if (!pref_parent) {
01937         return true;
01938     }
01939 
01940     dodag_info->parent_flags |= RPL_PRIMARY_PARENT_SET;
01941     memcpy(dodag_info->primary_parent,
01942            pref_parent->have_global_address ? pref_parent->global_address
01943            : pref_parent->ll_address,
01944            16);
01945     dodag_info->primary_parent_rank = pref_parent->rank;
01946 
01947     rpl_neighbour_t *sec_parent = ns_list_get_next(&instance->candidate_neighbours, pref_parent);
01948     if (!sec_parent || !sec_parent->dodag_parent) {
01949         return true;
01950     }
01951 
01952     dodag_info->parent_flags |= RPL_SECONDARY_PARENT_SET;
01953     memcpy(dodag_info->secondary_parent,
01954            sec_parent->have_global_address ? sec_parent->global_address
01955            : sec_parent->ll_address,
01956            16);
01957     dodag_info->secondary_parent_rank = sec_parent->rank;
01958 
01959     return true;
01960 }
01961 
01962 bool rpl_upward_accept_prefix_update(const rpl_dodag_t *dodag_info, const rpl_neighbour_t *neighbour, const rpl_neighbour_t *pref_parent)
01963 {
01964     //Accept allways from Pref parent or before it is selected
01965     if (!pref_parent || neighbour == pref_parent) {
01966         return true;
01967     }
01968 
01969     //Accept only same or higher version number
01970     if (rpl_dodag_version_compare(neighbour->dodag_version, pref_parent->dodag_version) & (RPL_CMP_EQUAL | RPL_CMP_GREATER)) {
01971         //Calculate Time between from last dio from parent and this neighbour
01972         //neighbour dio_timestamp >= pref_parent's, because it's a newly-received message
01973         uint32_t time_between_parent = neighbour->dio_timestamp - pref_parent->dio_timestamp;
01974         uint32_t accepted_time = rpl_dio_imax_time_calculate(dodag_info->dio_timer_params.Imax, 0x0200);
01975         //Accept prefix Update If Time from last DIO is more than 2 x Max
01976         if (accepted_time < time_between_parent) {
01977             return true;
01978         }
01979     }
01980 
01981     return false;
01982 }
01983 
01984 #endif /* HAVE_RPL */