Kenji Arai
/
mbed-os_TYBLE16
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Dependents: TYBLE16_simple_data_logger TYBLE16_MP3_Air
Embed:
(wiki syntax)
Show/hide line numbers
rpl_downward.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_downward.c deals with management of DAO targets, DAO parents, and 00019 * downward routes within an 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 * The rpl_dao_target_t type overloads different needs: 00027 * 1) Non-storing root storage, which needs to record transit addresses. 00028 * 2) Published targets - published either for ourselves or on behalf of 00029 * connected hosts. Sent to either DAO parents or DODAG root, depending 00030 * on mode. 00031 * 3) Storing-mode non-owned targets - those we've received from DAO 00032 * children, and need to forward on. 00033 * 00034 * Flags settings: 00035 * 00036 * 1) Root non-storing storage: root=Y published=N own=N 00037 * 2) Published: root=N published=Y own=Y/N 00038 * 3) Storing storage: root=N published=N own=N 00039 * 00040 * 00041 * We follow the Path Control logic as follows - we can have up to 8 DAO 00042 * Parents, and they are assigned specific Path Control bits, rather than 00043 * a whole group of parents being assigned to a whole Path Control subfield 00044 * as in RFC 6550. Assignments are derived automatically from the preference 00045 * field set by the objective function, limited by the Path Control Size. There 00046 * is no specific mechanism for the objective function to control DAO parents 00047 * separately from DIO parents. 00048 * 00049 * Examples: 00050 * Parent prefs Path Control assignments 00051 * 1 11111111 00052 * 00053 * 1,2 11000000,00111111 00054 * 00055 * 1,1 10000000,01111111 00056 * 00057 * 1,1,2,3,3 10000000,01000000,00110000,00001000,00000111 00058 * 00059 * 1,1,2 10000000,01000000,00111111 00060 * 00061 * 1,1,1 (treated as 1,1,2) 00062 * 00063 * If a parent is removed in Storing mode, we send it a No-Path for all 00064 * targets. (9.8.4) 00065 * 00066 * If a totally new parent is added to the DAO parent set, we can't really 00067 * do anything if we don't own the target (Storing mode only). I guess we could 00068 * send it an update if it is in a disjoint position? 00069 * 00070 * If we own the target (as we always will Non-Storing), we can trigger a path 00071 * sequence update to change parents - addition or removal. 00072 * 00073 * Targets contain 8-bit bitfields, which indicates which path control bits have 00074 * been registered. Parent choice happens at the instant of registration - we 00075 * just AND together parent and target path control bits. 00076 */ 00077 00078 #include "nsconfig.h" 00079 00080 #ifdef HAVE_RPL 00081 00082 #include <string.h> 00083 #include "common_functions.h" 00084 #include "ns_types.h" 00085 #include "ns_list.h" 00086 #include "ns_trace.h" 00087 #include "nsdynmemLIB.h" 00088 #include "randLIB.h" 00089 #include "ip6string.h" 00090 00091 #include "Common_Protocols/icmpv6.h" 00092 #include "NWK_INTERFACE/Include/protocol.h" 00093 #include "ipv6_stack/ipv6_routing_table.h" 00094 00095 #include "net_rpl.h" 00096 #include "RPL/rpl_protocol.h" 00097 #include "RPL/rpl_policy.h" 00098 #include "RPL/rpl_upward.h" 00099 #include "RPL/rpl_downward.h" 00100 #include "RPL/rpl_control.h" 00101 #include "RPL/rpl_data.h" 00102 #include "RPL/rpl_structures.h" 00103 00104 #define TRACE_GROUP "RPLd" 00105 00106 #ifdef HAVE_RPL_ROOT 00107 static void rpl_downward_topo_sort_invalidate(rpl_instance_t *instance); 00108 #endif 00109 00110 #define DEFAULT_DAO_DELAY 10 /* *100ms ticks = 1s */ 00111 00112 //#define MINIMUM_DAO_TARGET_REFRESH (5*60) /* seconds */ 00113 00114 /* Bit <n> of the PC mask */ 00115 #define PCBIT(n) (UINT8_C(0x80) >> (n)) 00116 00117 /* The PCS mask */ 00118 #define PCSMASK(pcs) ((uint8_t)(0x100 - PCBIT(pcs))) 00119 00120 00121 /* 00122 * 0 1 2 3 4 5 6 7 00123 * +-+-+-+-+-+-+-+-+ 00124 * |PC1|PC2|PC3|PC4| 00125 * +-+-+-+-+-+-+-+-+ 00126 * 00127 * Figure 27: Path Control Preference Subfield Encoding 00128 */ 00129 void rpl_downward_convert_dodag_preferences_to_dao_path_control(rpl_dodag_t *dodag) 00130 { 00131 if (!dodag || rpl_dodag_mop(dodag) == RPL_MODE_NO_DOWNWARD) { 00132 return; 00133 } 00134 00135 rpl_instance_t *instance = dodag->instance; 00136 uint8_t pcs = dodag->config.path_control_size; 00137 uint_fast8_t bit = 0; 00138 00139 rpl_neighbour_t *last = NULL; 00140 rpl_neighbour_t *neighbour = ns_list_get_first(&instance->candidate_neighbours); 00141 while (neighbour && neighbour->dodag_parent && bit <= pcs) { 00142 rpl_neighbour_t *next = ns_list_get_next(&instance->candidate_neighbours, neighbour); 00143 /* Terminate when we hit a non-DODAG parent */ 00144 if (next && !next->dodag_parent) { 00145 next = NULL; 00146 } 00147 00148 /* If non-storing, neighbours if they don't have a known global address */ 00149 if (!neighbour->have_global_address && rpl_dodag_mop(dodag) == RPL_MODE_NON_STORING) { 00150 neighbour = next; 00151 continue; 00152 } 00153 00154 neighbour->dao_path_control = PCBIT(bit++); 00155 if (bit <= pcs && next && next->dodag_pref > neighbour->dodag_pref && (bit & 1)) { 00156 /* Next neighbour is less-preferred, and would join us in the second 00157 * bit of our subfield. Expand this neighbour to use the second bit, 00158 * so next will be in the next subfield. 00159 */ 00160 neighbour->dao_path_control |= PCBIT(bit++); 00161 } 00162 last = neighbour; 00163 neighbour = next; 00164 } 00165 00166 /* If we didn't fill the Path Control, expand the final neighbour */ 00167 if (last) { 00168 while (bit <= pcs) { 00169 last->dao_path_control |= PCBIT(bit++); 00170 } 00171 } 00172 } 00173 00174 static void rpl_downward_target_refresh(rpl_dao_target_t *target) 00175 { 00176 target->need_seq_inc = true; 00177 target->info.non_root.pc_assigned = 0; 00178 target->info.non_root.pc_assigning = 0; 00179 target->info.non_root.pc_to_retry = 0; 00180 target->info.non_root.path_lifetime = 0; 00181 } 00182 00183 static bool rpl_instance_parent_selection_ready(rpl_instance_t *instance) 00184 { 00185 rpl_neighbour_t *neighbour = ns_list_get_first(&instance->candidate_neighbours); 00186 if (neighbour && neighbour->dodag_parent && neighbour->dao_path_control) { 00187 //We have a Primary parent with Dao patha control 00188 return true; 00189 } 00190 return false; 00191 } 00192 00193 void rpl_downward_neighbour_gone(rpl_instance_t *instance, rpl_neighbour_t *neighbour) 00194 { 00195 00196 // Currently don't need to do anything - caller is expected to 00197 // trigger parent selection, which will do everything required. 00198 (void) instance; 00199 (void) neighbour; 00200 } 00201 00202 void rpl_downward_process_dao_parent_changes(rpl_instance_t *instance) 00203 { 00204 bool storing; 00205 00206 switch (rpl_instance_mop(instance)) { 00207 case RPL_MODE_NON_STORING: 00208 storing = false; 00209 break; 00210 case RPL_MODE_STORING: 00211 case RPL_MODE_STORING_MULTICAST: 00212 storing = true; 00213 break; 00214 default: 00215 return; 00216 } 00217 00218 bool bits_removed = false; 00219 uint8_t bits_added = 0; 00220 00221 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00222 if (neighbour->old_dao_path_control != neighbour->dao_path_control) { 00223 if (neighbour->old_dao_path_control & ~ neighbour->dao_path_control) { 00224 bits_removed = true; 00225 break; 00226 } else { 00227 /* May as well resend all bits for this parent, not just new */ 00228 bits_added |= neighbour->dao_path_control; 00229 } 00230 } 00231 } 00232 00233 if (!(bits_removed || bits_added)) { 00234 return; 00235 } 00236 00237 tr_debug("removed=%x, added=%x", bits_removed, bits_added); 00238 00239 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00240 if (neighbour->dao_path_control != 0 && neighbour->old_dao_path_control == 0) { 00241 //Candidate has become a DAO parent 00242 rpl_control_event(instance->domain, RPL_EVENT_DAO_PARENT_ADD); 00243 break; 00244 } 00245 } 00246 00247 if (storing) { 00248 /* XXX more complicated - No-Paths to people losing stuff, etc. 00249 * Need to think a bit about what each parent would have had. 00250 * Different handling for stuff we own and stuff we don't. Can 00251 * probably actually unify somewhat, but needs thought. 00252 */ 00253 } else { 00254 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00255 if (target->published && target->own) { 00256 if (bits_removed) { 00257 /* Simple - just increment Path Sequence and trigger DAO to root */ 00258 rpl_downward_target_refresh(target); 00259 } else { 00260 /* Make sure we send the newly-added bits (would previously have been assigned to no-one) */ 00261 target->info.non_root.pc_assigned &= ~bits_added; 00262 } 00263 } 00264 } 00265 00266 //Trig DAO allways after change 00267 rpl_instance_dao_trigger(instance, 0); 00268 } 00269 } 00270 00271 rpl_dao_target_t *rpl_create_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len, bool root) 00272 { 00273 rpl_dao_target_t *target = rpl_alloc(sizeof(rpl_dao_target_t)); 00274 if (!target) { 00275 tr_warn("RPL DAO overflow (target=%s)", trace_ipv6_prefix(prefix, prefix_len)); 00276 return NULL; 00277 } 00278 memset(target, 0, sizeof * target); 00279 bitcopy0(target->prefix, prefix, prefix_len); 00280 target->instance = instance; 00281 target->prefix_len = prefix_len; 00282 target->path_sequence = rpl_seq_init(); 00283 target->root = root; 00284 #ifdef HAVE_RPL_ROOT 00285 if (root) { 00286 ns_list_init(&target->info.root.transits); 00287 } 00288 rpl_downward_topo_sort_invalidate(instance); 00289 #endif 00290 00291 ns_list_add_to_end(&instance->dao_targets, target); 00292 return target; 00293 } 00294 00295 void rpl_delete_dao_target(rpl_instance_t *instance, rpl_dao_target_t *target) 00296 { 00297 /* XXX For each notified parent, send a No-Path DAO */ 00298 00299 /* TODO - should send a No-Path to root */ 00300 00301 ns_list_remove(&instance->dao_targets, target); 00302 00303 #ifdef HAVE_RPL_ROOT 00304 if (target->root) { 00305 ns_list_foreach_safe(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 00306 ns_list_remove(&target->info.root.transits, transit); 00307 rpl_free(transit, sizeof * transit); 00308 } 00309 ipv6_route_table_remove_info(-1, ROUTE_RPL_DAO_SR, target); 00310 rpl_downward_topo_sort_invalidate(target->instance); 00311 } 00312 #endif 00313 rpl_free(target, sizeof * target); 00314 } 00315 00316 rpl_dao_target_t *rpl_instance_lookup_published_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00317 { 00318 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00319 if (target->published && target->prefix_len == prefix_len && 00320 bitsequal(target->prefix, prefix, prefix_len)) { 00321 return target; 00322 } 00323 } 00324 return NULL; 00325 } 00326 00327 rpl_dao_target_t *rpl_instance_lookup_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00328 { 00329 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00330 if (target->prefix_len == prefix_len && 00331 bitsequal(target->prefix, prefix, prefix_len)) { 00332 return target; 00333 } 00334 } 00335 return NULL; 00336 } 00337 00338 rpl_dao_target_t *rpl_instance_match_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00339 { 00340 rpl_dao_target_t *longest = NULL; 00341 int_fast16_t longest_len = -1; 00342 00343 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00344 if (target->prefix_len >= longest_len && target->prefix_len <= prefix_len && 00345 bitsequal(target->prefix, prefix, target->prefix_len)) { 00346 longest = target; 00347 longest_len = target->prefix_len; 00348 if (longest_len == 128) { 00349 break; 00350 } 00351 } 00352 } 00353 return longest; 00354 } 00355 void rpl_instance_delete_published_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00356 { 00357 rpl_dao_target_t *target = rpl_instance_lookup_published_dao_target(instance, prefix, prefix_len); 00358 if (target) { 00359 rpl_delete_dao_target(instance, target); 00360 } 00361 } 00362 00363 void rpl_instance_publish_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len, uint32_t valid_lifetime, bool own, bool want_descriptor, uint32_t descriptor) 00364 { 00365 rpl_dao_target_t *target = rpl_instance_lookup_published_dao_target(instance, prefix, prefix_len); 00366 if (target) { 00367 int diff = target->lifetime > valid_lifetime ? target->lifetime - valid_lifetime : valid_lifetime - target->lifetime; 00368 target->lifetime = valid_lifetime; 00369 if (!own && diff > 60) { 00370 /* For non-owned targets, publish triggers a refresh */ 00371 rpl_downward_target_refresh(target); 00372 rpl_instance_dao_trigger(instance, 0); 00373 } 00374 return; 00375 } 00376 target = rpl_create_dao_target(instance, prefix, prefix_len, false); 00377 if (!target) { 00378 tr_warn("Failed to publish DAO target %s", trace_ipv6_prefix(prefix, prefix_len)); 00379 return; 00380 } 00381 target->interface_id = -1; 00382 target->published = true; 00383 target->own = own; 00384 target->external = !own; 00385 target->lifetime = valid_lifetime; 00386 if (own) { 00387 target->info.non_root.refresh_timer = 0; /* Auto-refresh */ 00388 } else { 00389 target->info.non_root.refresh_timer = 0xFFFFFFFF; /* Do not refresh - require republishing */ 00390 } 00391 target->descriptor_present = want_descriptor; 00392 target->descriptor = descriptor; 00393 target->path_control = 0xFF; /* Use as much path control as we can (PCS limits) */ 00394 target->response_wait_time = 0; 00395 target->active_confirmation_state = false; 00396 target->trig_confirmation_state = true; 00397 //Activate allways registration 00398 instance->pending_neighbour_confirmation = rpl_policy_parent_confirmation_requested(); 00399 tr_debug("New Target %s", trace_ipv6(target->prefix)); 00400 /* Path lifetime left as 0 for now - will be filled in on transmission, along with refresh timer */ 00401 rpl_instance_dao_trigger(instance, 0); 00402 00403 } 00404 00405 void rpl_instance_dao_trigger(rpl_instance_t *instance, uint16_t delay) 00406 { 00407 if (delay == 0) { 00408 delay = randLIB_randomise_base(DEFAULT_DAO_DELAY, 0x4000, 0xC000); 00409 } 00410 if (instance->delay_dao_timer == 0 || instance->delay_dao_timer > delay) { 00411 instance->delay_dao_timer = delay; 00412 //tr_debug("DAO trigger %" PRIu16, delay); 00413 } 00414 } 00415 00416 /* 00417 * 0 1 2 3 00418 * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 00419 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00420 * | Type = 0x05 | Option Length | Flags | Prefix Length | 00421 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00422 * | | 00423 * + + 00424 * | Target Prefix (Variable Length) | 00425 * . . 00426 * . . 00427 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00428 * 00429 * Figure 25: Format of the RPL Target Option 00430 * 00431 * 0 1 2 3 00432 * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 00433 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00434 * | Type = 0x09 |Opt Length = 4 | Descriptor 00435 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00436 * Descriptor (cont.) | 00437 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00438 * 00439 * Figure 30: Format of the RPL Target Descriptor Option 00440 */ 00441 static uint8_t *rpl_downward_write_target(uint8_t *ptr, rpl_dao_target_t *target) 00442 { 00443 uint8_t byte_len = (target->prefix_len + 7u) / 8u; 00444 *ptr++ = RPL_TARGET_OPTION; 00445 *ptr++ = 2 + byte_len; 00446 *ptr++ = 0; // flags 00447 *ptr++ = target->prefix_len; 00448 bitcopy0(ptr, target->prefix, target->prefix_len); 00449 ptr += byte_len; 00450 00451 if (target->descriptor_present) { 00452 *ptr++ = RPL_TARGET_DESC_OPTION; 00453 *ptr++ = 4; 00454 ptr = common_write_32_bit(target->descriptor, ptr); 00455 } 00456 00457 return ptr; 00458 } 00459 /* 00460 * 0 1 2 3 00461 * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 00462 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00463 * | Type = 0x06 | Option Length |E| Flags | Path Control | 00464 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00465 * | Path Sequence | Path Lifetime | | 00466 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 00467 * | | 00468 * + + 00469 * | | 00470 * + Parent Address* + 00471 * | | 00472 * + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00473 * | | 00474 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00475 * 00476 * Figure 26: Format of the Transit Information Option 00477 * 00478 */ 00479 static uint8_t *rpl_downward_write_transit(uint8_t *ptr, rpl_dao_target_t *target, uint8_t path_control, const uint8_t *parent, bool no_path) 00480 { 00481 *ptr++ = RPL_TRANSIT_OPTION; 00482 *ptr++ = parent ? 16 + 4 : 4; 00483 *ptr++ = target->external ? TRANSIT_FLAG_EXTERNAL : 0; 00484 *ptr++ = path_control; 00485 *ptr++ = target->path_sequence; 00486 *ptr++ = no_path ? 0 : target->info.non_root.path_lifetime; 00487 if (parent) { 00488 ptr = (uint8_t *) memcpy(ptr, parent, 16) + 16; 00489 } 00490 00491 return ptr; 00492 } 00493 00494 static bool rpl_instance_clear_target_pc_to_retry(rpl_instance_t *instance) 00495 { 00496 bool had_retry = false; 00497 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00498 if (!target->root && target->info.non_root.pc_to_retry) { 00499 target->info.non_root.pc_to_retry = 0; 00500 had_retry = true; 00501 } 00502 } 00503 00504 return had_retry; 00505 } 00506 00507 /* Find a target that needs updating. For storing mode, after first is found, 00508 * subsequent must be for the same parent. 00509 */ 00510 static rpl_dao_target_t *rpl_instance_choose_target_to_assign(rpl_instance_t *instance, bool storing, rpl_neighbour_t **parent, uint8_t *path_control, rpl_dao_target_t *t1) 00511 { 00512 retry: 00513 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00514 if (target->root || target == t1) { 00515 continue; 00516 } 00517 00518 /* Check if this target has any unassigned path control bits */ 00519 uint8_t unassigned_pc = target->path_control & ~(target->info.non_root.pc_assigned | target->info.non_root.pc_assigning | target->info.non_root.pc_to_retry); 00520 if (!unassigned_pc) { 00521 continue; 00522 } 00523 00524 /* If we are looking for a follow-up target to share transit, transit data must match */ 00525 if (t1) { 00526 uint8_t target_seq = target->path_sequence; 00527 if (target->need_seq_inc) { 00528 target_seq = rpl_seq_inc(target_seq); 00529 } 00530 if (target->external != t1->external || target->own != t1->own || 00531 target_seq != t1->path_sequence || 00532 target->info.non_root.path_lifetime != t1->info.non_root.path_lifetime) { 00533 continue; 00534 } 00535 } 00536 00537 /* unassigned_pc is the total path control needing assignment */ 00538 if (!storing) { 00539 /* In non-storing mode, any number of targets+transits can be output to root in 1 DAO */ 00540 /* Leave unassigned_pc as the entire path control across all parents */ 00541 } else if (*parent == NULL) { 00542 /* In storing mode, need to choose a parent, if we haven't already */ 00543 /* This is the very first target for the DAO - we now choose a parent that wants 00544 * the bits, and output that parent's path control so we use it for future targets. 00545 */ 00546 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00547 if (neighbour->dao_path_control & unassigned_pc) { 00548 unassigned_pc &= neighbour->dao_path_control; 00549 *path_control = unassigned_pc; 00550 *parent = neighbour; 00551 return target; 00552 } 00553 } 00554 } else { 00555 /* This is not the first target - we must be picking subsequent 00556 * targets with unassigned bits for the parent we chose last time. 00557 */ 00558 unassigned_pc &= (*parent)->dao_path_control; 00559 if (!unassigned_pc) { 00560 continue; 00561 } 00562 } 00563 00564 /* If looking for a follow-up target, final path control must match */ 00565 if (t1) { 00566 if (unassigned_pc != *path_control) { 00567 continue; 00568 } 00569 } else { 00570 *path_control = unassigned_pc; 00571 } 00572 return target; 00573 } 00574 00575 if (!t1) { 00576 /* If found nothing on initial search, it would appear we're done. However, 00577 * we were skipping "to_retry" assignments. Clear to_retry flags, and if 00578 * there were any, retry. We currently retry indefinitely (but with 00579 * exponential backoff). 00580 */ 00581 if (rpl_instance_clear_target_pc_to_retry(instance)) { 00582 if (instance->dao_attempt < 255) { 00583 ++instance->dao_attempt; 00584 } 00585 tr_warn("DAO retry, attempt %d", instance->dao_attempt); 00586 goto retry; 00587 } 00588 } 00589 return NULL; 00590 } 00591 00592 static void rpl_downward_reset_assigning(rpl_instance_t *instance, uint8_t pcs_mask) 00593 { 00594 uint8_t parent_mask = 0; 00595 /* Check to see if we're short of parent mask coverage. If so, remove bits from the mask */ 00596 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00597 parent_mask |= neighbour->dao_path_control; 00598 } 00599 pcs_mask &= parent_mask; 00600 00601 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00602 target->info.non_root.pc_assigning = 0; 00603 /* For ease of processing, we allow target path control to have bits 00604 * beyond the mask. In this pass, we quietly mark those bits as 00605 * "assigned", as if we've sent them to an invisible parent. 00606 */ 00607 target->info.non_root.pc_assigned |= (target->path_control & ~pcs_mask); 00608 target->info.non_root.pc_to_retry &= pcs_mask; 00609 } 00610 } 00611 00612 static void rpl_instance_unconfirm_parent_info(rpl_instance_t *instance) 00613 { 00614 ns_list_foreach_safe(rpl_neighbour_t, n, &instance->candidate_neighbours) { 00615 if (n->dao_path_control == 0) { 00616 continue; 00617 } 00618 n->confirmed = false; 00619 00620 } 00621 } 00622 00623 static rpl_dao_target_t *rpl_instance_get_pending_target_confirmation_for_address(rpl_instance_t *instance, const uint8_t address [16]) 00624 { 00625 ns_list_foreach_safe(rpl_dao_target_t, n, &instance->dao_targets) { 00626 if (memcmp(n->prefix, address, 16) == 0) { 00627 return n; 00628 } 00629 } 00630 return NULL; 00631 } 00632 00633 static rpl_dao_target_t *rpl_instance_get_pending_target_confirmation(rpl_instance_t *instance) 00634 { 00635 ns_list_foreach_safe(rpl_dao_target_t, n, &instance->dao_targets) { 00636 if (!n->trig_confirmation_state) { 00637 continue; 00638 } 00639 n->trig_confirmation_state = false; 00640 n->active_confirmation_state = true; 00641 instance->wait_response = NULL; 00642 rpl_instance_unconfirm_parent_info(instance); 00643 return n; 00644 } 00645 return NULL; 00646 } 00647 00648 void rpl_instance_send_address_registration(rpl_instance_t *instance, const uint8_t addr[16]) 00649 { 00650 if (!rpl_instance_parent_selection_ready(instance)) { 00651 return; 00652 } 00653 00654 00655 if (addr) { 00656 rpl_dao_target_t *target = rpl_instance_get_pending_target_confirmation_for_address(instance, addr); 00657 if (!target) { 00658 return; 00659 } 00660 00661 if (instance->pending_neighbour_confirmation && (target->active_confirmation_state || target->trig_confirmation_state)) { 00662 return; 00663 } 00664 target->trig_confirmation_state = true; 00665 } else if (!instance->pending_neighbour_confirmation) { 00666 ns_list_foreach_safe(rpl_dao_target_t, n, &instance->dao_targets) { 00667 n->trig_confirmation_state = true; 00668 } 00669 } 00670 instance->pending_neighbour_confirmation = true; 00671 } 00672 00673 00674 /* We are optimised for sending updates to existing targets to current parents; 00675 * we track the state of what information DAO parents have, and manage the 00676 * updates together with message coalescing and ack tracking. 00677 * 00678 * No-Paths are handled separately, and not tracked - we spit out No-Paths 00679 * at the moment targets or parents are deleted, 1 attempt only. 00680 * 00681 * This function only has to deals with updating our active state. 00682 */ 00683 void rpl_instance_send_dao_update(rpl_instance_t *instance) 00684 { 00685 instance->delay_dao_timer = 0; 00686 00687 rpl_dodag_t *dodag = rpl_instance_current_dodag(instance); 00688 if (!dodag || rpl_dodag_am_root(dodag)) { 00689 return; 00690 } 00691 00692 uint8_t mop = rpl_dodag_mop(dodag); 00693 bool storing; 00694 00695 switch (mop) { 00696 case RPL_MODE_NON_STORING: 00697 storing = false; 00698 break; 00699 case RPL_MODE_STORING: 00700 case RPL_MODE_STORING_MULTICAST: 00701 storing = true; 00702 break; 00703 default: 00704 return; 00705 } 00706 00707 //Verify that no pending address registartion to parent 00708 if (instance->pending_neighbour_confirmation) { 00709 rpl_instance_dao_trigger(instance, 6 * 10); 00710 return; 00711 } 00712 00713 if (instance->dao_in_transit) { 00714 // Force current DAO timeout to be cut short, then 00715 // when it times out, it will re-evaluate the situation, 00716 // and come back back here. 00717 uint16_t delay = rpl_policy_initial_dao_ack_wait(instance->domain, mop); 00718 if (instance->dao_retry_timer > delay) { 00719 instance->dao_retry_timer = delay; 00720 } 00721 return; 00722 } 00723 00724 if (rpl_policy_dao_retry_count() > 0 && instance->dao_attempt >= rpl_policy_dao_retry_count()) { 00725 // Check if recovery logic is started 00726 // after half the retries are done we remove the primary parent 00727 tr_info("DAO remove primary parent"); 00728 rpl_neighbour_t *neighbour = ns_list_get_first(&instance->candidate_neighbours); 00729 if (neighbour) { 00730 rpl_delete_neighbour(instance, neighbour); 00731 } 00732 // Set parameters to restart 00733 instance->dao_in_transit = false; 00734 instance->dao_attempt = 0; 00735 instance->dao_retry_timer = 0; 00736 instance->delay_dao_timer = 0; 00737 return; 00738 } 00739 00740 /* Which parent this DAO will be for if storing */ 00741 rpl_neighbour_t *parent = NULL; 00742 00743 /* Need our address to publish DAOs of attached hosts */ 00744 const uint8_t *our_addr = NULL; 00745 if (!storing) { 00746 ns_list_foreach(rpl_dao_target_t, t, &instance->dao_targets) { 00747 if (t->published && t->own && t->prefix_len == 128) { 00748 our_addr = t->prefix; 00749 break; 00750 } 00751 } 00752 } 00753 00754 /* To avoid packet overflow, we set a fairly conservative limit of how 00755 * many targets to put in a message. 00756 * 00757 * For storing mode, format is: 00758 * Base (4-20) 00759 * //Target (4-20, typically 20) 00760 * |\Descriptor (0-6) 00761 * |(^Repeat if more targets with same transit info) 00762 * \ Transit (6) 00763 * (^ Repeat if more targets for same parent, with different transit info) 00764 * 00765 * For non-storing mode, format is: 00766 * Base 00767 * //Target (4-20, typically 20) 00768 * |\Descriptor (0-6) 00769 * |(^Repeat if more targets with same transit info) 00770 * | Transit for parent 1 (22) 00771 * | Transit for parent 2 (22) 00772 * \ Transit... (22) (max 8 = 176 per target set) 00773 * (^ Repeat if more targets with different transit info/parents) 00774 */ 00775 00776 00777 uint8_t *opts = ns_dyn_mem_temporary_alloc(1280); 00778 if (!opts) { 00779 rpl_instance_dao_trigger(instance, 0); 00780 return; 00781 } 00782 uint8_t *ptr = opts; 00783 00784 rpl_downward_reset_assigning(instance, PCSMASK(dodag->config.path_control_size)); 00785 00786 ns_list_foreach(rpl_dao_target_t, t, &instance->dao_targets) { 00787 /* Self-published targets can defer path lifetime choice */ 00788 if (t->info.non_root.path_lifetime == 0) { 00789 uint32_t lifetime = t->lifetime; 00790 const rpl_dodag_conf_t *conf = rpl_dodag_get_config(dodag); 00791 uint16_t unit = conf->lifetime_unit; 00792 uint8_t def = conf->default_lifetime; 00793 if (lifetime != 0xFFFFFFFF) { 00794 lifetime = (lifetime + unit - 1) / unit; 00795 } 00796 if (lifetime > def) { 00797 lifetime = def; 00798 } 00799 t->info.non_root.path_lifetime = lifetime; 00800 } 00801 } 00802 00803 00804 /* We keep going until size exceeds 768. This gives plenty of slop to fit 00805 * in a 1280-byte packet. 00806 */ 00807 while (ptr < opts + 768) { 00808 uint8_t path_control; 00809 /* Find a target that needs an update - after the first, it must be for the current parent */ 00810 rpl_dao_target_t *target = rpl_instance_choose_target_to_assign(instance, storing, &parent, &path_control, NULL); 00811 if (!target) { 00812 break; 00813 } 00814 00815 /* Stupid error case - can't publish non-owned addresses if we don't know our own address */ 00816 if (!storing && !target->own && !our_addr) { 00817 target->info.non_root.pc_assigned |= path_control; 00818 continue; 00819 } 00820 00821 if (target->need_seq_inc) { 00822 target->path_sequence = rpl_seq_inc(target->path_sequence); 00823 target->need_seq_inc = false; 00824 } 00825 00826 ptr = rpl_downward_write_target(ptr, target); 00827 target->info.non_root.pc_assigning = path_control; 00828 00829 /* Then find more targets with the same transit info - can compress */ 00830 while (ptr < opts + 768) { 00831 rpl_dao_target_t *t2 = rpl_instance_choose_target_to_assign(instance, storing, &parent, &path_control, target); 00832 if (!t2) { 00833 break; 00834 } 00835 t2->path_sequence = target->path_sequence; 00836 t2->need_seq_inc = false; 00837 t2->info.non_root.pc_assigning = path_control; 00838 ptr = rpl_downward_write_target(ptr, t2); 00839 } 00840 00841 /* Then output the transit information for the original target */ 00842 if (storing) { 00843 /* Just one transit info */ 00844 ptr = rpl_downward_write_transit(ptr, target, path_control, NULL, false); 00845 } else if (target->own) { 00846 /* One transit info for each DAO parent */ 00847 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00848 if (neighbour->dao_path_control & path_control) { 00849 ptr = rpl_downward_write_transit(ptr, target, neighbour->dao_path_control & path_control, neighbour->global_address, false); 00850 } 00851 } 00852 } else { 00853 /* Attached host - single transit is us */ 00854 ptr = rpl_downward_write_transit(ptr, target, path_control, our_addr, false); 00855 } 00856 } 00857 00858 if (ptr == opts) { 00859 /* Had nothing... */ 00860 ns_dyn_mem_free(opts); 00861 return; 00862 } 00863 00864 const uint8_t *dst; 00865 protocol_interface_info_entry_t *cur; 00866 if (storing) { 00867 dst = parent->ll_address; 00868 cur = protocol_stack_interface_info_get_by_id(parent->interface_id); 00869 } else { 00870 dst = dodag->id; 00871 cur = NULL; 00872 } 00873 00874 if (instance->dao_attempt > 0) { 00875 // Start informing problem in routing. This will cause us to select secondary routes when sending the DAO 00876 tr_info("DAO reachability problem"); 00877 protocol_interface_info_entry_t *interface = protocol_stack_interface_info_get_by_rpl_domain(instance->domain, -1); 00878 if (interface) { 00879 ipv6_neighbour_reachability_problem(dst, interface->id); 00880 } 00881 } 00882 00883 bool need_ack = rpl_control_transmit_dao(instance->domain, cur, instance, instance->id, instance->dao_sequence, dodag->id, opts, ptr - opts, dst); 00884 ns_dyn_mem_free(opts); 00885 00886 instance->dao_sequence_in_transit = instance->dao_sequence; 00887 instance->dao_sequence = rpl_seq_inc(instance->dao_sequence); 00888 instance->requested_dao_ack = need_ack; 00889 instance->dao_in_transit = true; 00890 if (instance->dao_attempt < 16) { 00891 uint32_t t = (uint32_t) rpl_policy_initial_dao_ack_wait(instance->domain, mop) << instance->dao_attempt; 00892 t = randLIB_randomise_base(t, 0x4000, 0xC000); 00893 instance->dao_retry_timer = t <= 0xffff ? t : 0xffff; 00894 } else { 00895 instance->dao_retry_timer = 0xffff; 00896 } 00897 tr_info("DAO tx %u seq attempts %u retry-timer %u", instance->dao_sequence_in_transit, instance->dao_attempt, instance->dao_retry_timer); 00898 } 00899 00900 #if 0 00901 /* This only sends a specific No-Path for one target, to one neighbour, in storing mode */ 00902 void rpl_instance_send_dao_no_path(rpl_instance_t *instance, rpl_dao_target_t *target, rpl_neighbour_t *neighbour) 00903 { 00904 //rpl_control_transmit(domain, NULL, ICMPV6_CODE_RPL_DAO, buf, dst); 00905 uint8_t dodagid = rpl_instance_id_is_local(instance->id) ? RPL_DAO_FLAG_DODAGID : 0; 00906 uint8_t base_size = dodagid ? 4 + 16 : 4; 00907 uint16_t opts_size = 20 + 6 + 6; /* Worst case - Target/Desc/Transit */ 00908 buffer_t *buf = buffer_get(base_size + opts_size); 00909 if (!buf) { 00910 /* Retrigger? */ 00911 return; 00912 } 00913 uint8_t *ptr = buffer_data_pointer(buf); 00914 00915 ptr[0] = instance->id; 00916 ptr[1] = dodagid; 00917 ptr[2] = 0; 00918 ptr[3] = instance->dao_sequence = rpl_seq_inc(instance->dao_sequence); 00919 if (dodagid) { 00920 memcpy(ptr + 4, dodag->id, 16); 00921 ptr += 16; 00922 } 00923 ptr = rpl_downward_write_target(ptr, target); 00924 ptr = rpl_downward_write_transit(ptr, target, path_control ?, NULL, false); 00925 memcpy(buf + base_size, ptr, opts_size); 00926 const uint8_t *dst; 00927 if (storing) { 00928 dst = get_parent_ll_address(parent_idx); 00929 } else { 00930 dst = dodag->id; 00931 } 00932 rpl_control_transmit(domain, NULL, ICMPV6_CODE_RPL_DAO, buf, neighbour->ll_address); 00933 } 00934 #endif 00935 00936 #ifdef HAVE_RPL_ROOT 00937 static uint_fast8_t rpl_downward_path_control_to_preference(uint8_t pc) 00938 { 00939 if (pc >= 0x40) { 00940 return 1; 00941 } else if (pc >= 0x10) { 00942 return 2; 00943 } else if (pc >= 0x04) { 00944 return 3; 00945 } else { 00946 return 4; 00947 } 00948 } 00949 00950 static rpl_dao_root_transit_t *rpl_downward_add_root_transit(rpl_dao_target_t *target, const uint8_t parent[16], uint8_t path_control) 00951 { 00952 //rpl_dao_root_transit_t *old_first = ns_list_get_first(&target->info.root.transits); 00953 rpl_dao_root_transit_t *transit = NULL; 00954 ns_list_foreach(rpl_dao_root_transit_t, t, &target->info.root.transits) { 00955 if (addr_ipv6_equal(t->transit, parent)) { 00956 ns_list_remove(&target->info.root.transits, t); 00957 transit = t; 00958 /* Updating existing transit - invalidates costs only */ 00959 rpl_downward_paths_invalidate(target->instance); 00960 break; 00961 } 00962 } 00963 00964 if (!transit) { 00965 transit = rpl_alloc(sizeof(rpl_dao_root_transit_t)); 00966 if (!transit) { 00967 tr_warn("RPL DAO overflow (target=%s,transit=%s)", trace_ipv6_prefix(target->prefix, target->prefix_len), trace_ipv6(parent)); 00968 goto out; 00969 } 00970 transit->path_control = 0; 00971 /* A new transit invalidates the topo sort */ 00972 rpl_downward_topo_sort_invalidate(target->instance); 00973 } 00974 00975 transit->target = target; 00976 transit->path_control |= path_control; 00977 /* Initial transit cost is 1-4, depending on preference in Path Control. 00978 * Source routing errors from intermediate nodes may increase this. For 00979 * directly connected nodes, rpl_downward_compute_paths asks policy 00980 * to modify according to ETX (or whatever). 00981 */ 00982 transit->cost = rpl_downward_path_control_to_preference(transit->path_control); 00983 00984 memcpy(transit->transit, parent, 16); 00985 ns_list_add_to_end(&target->info.root.transits, transit); 00986 00987 out: 00988 return ns_list_get_first(&target->info.root.transits); 00989 } 00990 00991 static rpl_dao_target_t *rpl_downward_delete_root_transit(rpl_dao_target_t *target, rpl_dao_root_transit_t *transit) 00992 { 00993 ns_list_remove(&target->info.root.transits, transit); 00994 rpl_free(transit, sizeof * transit); 00995 if (ns_list_is_empty(&target->info.root.transits)) { 00996 rpl_delete_dao_target(target->instance, target); 00997 return NULL; 00998 } 00999 01000 rpl_downward_topo_sort_invalidate(target->instance); 01001 return target; 01002 } 01003 01004 void rpl_downward_transit_error(rpl_instance_t *instance, const uint8_t *target_addr, const uint8_t *transit_addr) 01005 { 01006 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01007 if (!target->root) { 01008 continue; 01009 } 01010 if (!bitsequal(target_addr, target->prefix, target->prefix_len)) { 01011 continue; 01012 } 01013 ns_list_foreach_safe(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01014 if (addr_ipv6_equal(transit_addr, transit->transit)) { 01015 /* 4 bit Path Control gives us an initial 1-4 cost. We then add something for every error. */ 01016 /* This should make lowest path cost algorithm cycle through alternatives */ 01017 /* When the DAO is refreshed, the cost is reset, so we forget accumulated errors. */ 01018 if (transit->cost < 0xFFFC) { 01019 transit->cost += 4; 01020 } else { 01021 transit->cost = 0xFFFF; 01022 } 01023 rpl_downward_paths_invalidate(instance); 01024 instance->srh_error_count++; 01025 if (rpl_policy_dao_trigger_after_srh_error(instance->domain, (protocol_core_monotonic_time - instance->last_dao_trigger_time) / 10, instance->srh_error_count, ns_list_count(&instance->dao_targets))) { 01026 rpl_instance_increment_dtsn(instance); 01027 } 01028 break; 01029 } 01030 } 01031 } 01032 } 01033 #endif // HAVE_RPL_ROOT 01034 01035 #ifdef HAVE_RPL_DAO_HANDLING 01036 static bool rpl_downward_process_targets_for_transit(rpl_dodag_t *dodag, bool storing, const uint8_t *src, int8_t interface_id, const uint8_t *target_start, const uint8_t *target_end, const uint8_t *transit_opt, bool *new_info, uint8_t *status) 01037 { 01038 (void) status; 01039 const uint8_t *parent; 01040 /* Check transit length */ 01041 if (storing) { 01042 if (transit_opt[1] != 4) { 01043 return false; 01044 } 01045 parent = NULL; 01046 } else { 01047 if (transit_opt[1] != 20) { 01048 return false; 01049 } 01050 parent = transit_opt + 6; 01051 } 01052 bool external = transit_opt[2] & TRANSIT_FLAG_EXTERNAL; 01053 uint8_t path_control = transit_opt[3]; 01054 uint8_t path_sequence = transit_opt[4]; 01055 uint8_t path_lifetime = transit_opt[5]; 01056 01057 uint32_t lifetime; 01058 if (path_lifetime == 0xFF) { 01059 lifetime = 0xFFFFFFFF; 01060 } else { 01061 lifetime = (uint32_t) path_lifetime * dodag->config.lifetime_unit; 01062 } 01063 01064 rpl_dao_target_t *last_target = NULL; 01065 while (target_start < target_end) { 01066 switch (target_start[0]) { 01067 case RPL_TARGET_OPTION: { 01068 last_target = NULL; 01069 uint8_t prefix_len = target_start[3]; 01070 if (prefix_len > 128 || prefix_len > (target_start[1] - 2) * 8) { 01071 return false; 01072 } 01073 const uint8_t *prefix = target_start + 4; 01074 rpl_dao_target_t *target = rpl_instance_lookup_dao_target(dodag->instance, prefix, prefix_len); 01075 if (target) { 01076 /* Ignore DAOs for targets we're publishing ourselves */ 01077 if (target->published) { 01078 break; 01079 } 01080 /* No-Paths are special: version number isn't significant */ 01081 if (path_lifetime == 0) { 01082 tr_info("No-Path %s->%s", parent ? trace_ipv6(parent) : "", trace_ipv6_prefix(prefix, prefix_len)); 01083 if (storing) { 01084 ipv6_route_delete_with_info(prefix, prefix_len, interface_id, src, ROUTE_RPL_DAO, target, 0); 01085 /* If we have no DAO routes left for this target, kill it (we don't track who sends individual 01086 * DAOs in our target database - the only record we have is in the system routing table 01087 */ 01088 if (!ipv6_route_lookup_with_info(prefix, prefix_len, interface_id, NULL, ROUTE_RPL_DAO, target, 0)) { 01089 rpl_delete_dao_target(dodag->instance, target); 01090 *new_info = true; 01091 } 01092 } else { 01093 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01094 if (addr_ipv6_equal(transit->transit, parent)) { 01095 target = rpl_downward_delete_root_transit(target, transit); 01096 *new_info = true; 01097 break; 01098 } 01099 } 01100 } 01101 /* No more processing on this target - go to next option */ 01102 break; 01103 } 01104 /* A real path. Compare path sequence. */ 01105 rpl_cmp_t seq_cmp = rpl_seq_compare(path_sequence, target->path_sequence); 01106 01107 bool accept; 01108 if (storing) { 01109 /* For storing, follow the letter of spec. Can't afford for old route propagation to happen. */ 01110 accept = seq_cmp & (RPL_CMP_GREATER | RPL_CMP_EQUAL); 01111 } else { 01112 /* Lollipop counters don't necessarily work brilliantly after reboot - the path 01113 * sequence causes more problems than it solves for non-storing modes, where it's 01114 * the actual target owner sending the info. We don't have to worry about the 01115 * network storing stale data. So we're more flexible. 01116 */ 01117 if (path_sequence >= 128) { 01118 /* Always accept anything with sequence in the lollipop counter restart region */ 01119 accept = true; 01120 /* Also, we always refresh lifetime, even if sequence number is the same as stored */ 01121 target->lifetime = lifetime; 01122 } else if (external) { 01123 /* ZigBee IP requires external targets to use latest info and ignore sequence - 01124 * publishers can't really keep them in sync. We go along with this. 01125 */ 01126 accept = true; 01127 target->lifetime = lifetime; 01128 } else { 01129 accept = seq_cmp & (RPL_CMP_GREATER | RPL_CMP_EQUAL); 01130 } 01131 } 01132 if (!accept) { 01133 tr_info("Ignoring stale path %s->%s (seq=%d vs %d)", parent ? trace_ipv6(parent) : "", trace_ipv6_prefix(prefix, prefix_len), path_sequence, target->path_sequence); 01134 break; 01135 } 01136 /* If path sequence is different, we clear existing transits for this target */ 01137 if (!(seq_cmp & RPL_CMP_EQUAL)) { 01138 if (target->root) { 01139 ns_list_foreach_safe(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01140 ns_list_remove(&target->info.root.transits, transit); 01141 rpl_free(transit, sizeof * transit); 01142 } 01143 } 01144 if (storing) { 01145 ipv6_route_table_remove_info(-1, ROUTE_RPL_DAO, target); 01146 } 01147 target->path_control = 0; 01148 target->path_sequence = path_sequence; 01149 target->lifetime = lifetime; 01150 *new_info = true; 01151 } 01152 /* Then we proceed to add this transit to the target below */ 01153 } else if (path_lifetime != 0) { 01154 target = rpl_create_dao_target(dodag->instance, prefix, prefix_len, !storing); 01155 if (target) { 01156 target->path_sequence = path_sequence; 01157 target->lifetime = lifetime; 01158 } 01159 } 01160 01161 /* No-Paths don't reach here - we break out above */ 01162 if (target) { 01163 if (path_control & ~ target->path_control) { 01164 target->path_control |= path_control; 01165 *new_info = true; 01166 } 01167 target->external = external; 01168 target->interface_id = interface_id; 01169 if (storing) { 01170 target->info.non_root.path_lifetime = path_lifetime; 01171 } 01172 01173 if (storing) { 01174 /* In Storing mode, add a route immediately */ 01175 ipv6_route_add_with_info(prefix, prefix_len, interface_id, src, ROUTE_RPL_DAO, target, 0, target->lifetime, 0); 01176 } else { 01177 rpl_dao_root_transit_t *transit = rpl_downward_add_root_transit(target, parent, path_control); 01178 #if 0 01179 /* In Non-Storing mode, add the transit to the target, and we'll re-evaluate system routes later */ 01180 ipv6_route_table_remove_info(-1, ROUTE_RPL_DAO_SR, target); 01181 if (transit_opt) { 01182 if (protocol_interface_address_compare(parent) == 0) { 01183 /* If we're transit, it's on-link */ 01184 ipv6_route_add_with_info(prefix, prefix_len, interface_id, NULL, ROUTE_RPL_DAO_SR, target, 0, target->lifetime, 0); 01185 } else { 01186 ipv6_route_add_with_info(prefix, prefix_len, interface_id, parent, ROUTE_RPL_DAO_SR, target, 0, target->lifetime, 0); 01187 } 01188 } 01189 #else 01190 if (transit) { 01191 ipv6_route_add_with_info(prefix, prefix_len, interface_id, ADDR_UNSPECIFIED, ROUTE_RPL_DAO_SR, target, 0, target->lifetime, 0); 01192 } 01193 #endif 01194 } 01195 } 01196 01197 last_target = target; 01198 break; 01199 } 01200 case RPL_TARGET_DESC_OPTION: 01201 if (target_start[1] == 4 && last_target) { 01202 last_target->descriptor_present = true; 01203 last_target->descriptor = common_read_32_bit(target_start + 2); 01204 } 01205 break; 01206 case RPL_PAD1_OPTION: 01207 target_start++; 01208 continue; 01209 } 01210 target_start += 2 + target_start[1]; 01211 } 01212 01213 return true; 01214 } 01215 #endif // HAVE_RPL_DAO_HANDLING 01216 01217 #ifdef HAVE_RPL_ROOT 01218 /* Link the graph ready for routing. "Canonical" database information stores 01219 * transits per target - in effect edges from children to parents. 01220 * For our path finding we need to match transits by prefix - eg all 2002::xx 01221 * transits might go via one 2002::/64 target - and we want to turn it around 01222 * so that our edges point from parents to children. 01223 * 01224 * This fills in (from scratch): 01225 * 01226 * transit::parent :-> matched target, or NULL for disconnected/DODAG root (us) 01227 * 01228 * target::connected := true for targets directly connected to DODAG root 01229 * 01230 * target::info.root.children 01231 * and instance::root_children := list of transits with this target/root as parent 01232 * 01233 * target::info.root.cost := number of transits connected to parent targets (connections to root not included) 01234 */ 01235 static void rpl_downward_link_transits_to_targets(rpl_instance_t *instance) 01236 { 01237 ns_list_init(&instance->root_children); 01238 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01239 target->info.root.cost = 0; 01240 target->connected = false; 01241 ns_list_init(&target->info.root.children); 01242 } 01243 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01244 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01245 if (protocol_interface_address_compare(transit->transit) == 0) { 01246 /* It points to us (the DODAG root) - mark this with NULL */ 01247 transit->parent = NULL; 01248 target->connected = true; 01249 /* Links to the root don't count as incoming transits */ 01250 ns_list_add_to_end(&instance->root_children, transit); 01251 } else { 01252 transit->parent = rpl_instance_match_dao_target(instance, transit->transit, 128); 01253 if (transit->parent) { 01254 target->info.root.cost++; 01255 ns_list_add_to_end(&transit->parent->info.root.children, transit); 01256 } 01257 } 01258 } 01259 } 01260 } 01261 01262 /* Subroutine for topo sort - an edge has been removed, either because the 01263 * parent is moved to the sorted list, or we're breaking a loop. Update 01264 * the "incoming edges" count in the child, and maybe move it to the top nodes list. 01265 */ 01266 static void rpl_downward_topo_sort_edge_removed(rpl_dao_root_transit_t *transit, rpl_dao_target_list_t *graph, rpl_dao_target_list_t *top_nodes) 01267 { 01268 rpl_dao_target_t *child = transit->target; 01269 01270 if (child->info.root.cost > 0) { 01271 child->info.root.cost--; 01272 } else { 01273 tr_err("topo sort count error"); 01274 } 01275 /* If this child has no more incoming, move it onto the "top nodes" list */ 01276 if (child->info.root.cost == 0) { 01277 ns_list_remove(graph, child); 01278 ns_list_add_to_end(top_nodes, child); 01279 } 01280 } 01281 01282 static void rpl_downward_topo_sort_break_loop(rpl_dao_target_list_t *graph, rpl_dao_target_list_t *top_nodes) 01283 { 01284 rpl_dao_root_transit_t *kill_transit = NULL; 01285 01286 /* Don't expect this to happen much, so not particularly optimised - we kill 1 transit to break the loop */ 01287 /* First choose a target with the most transits - we want to delete spare ones. */ 01288 ns_list_foreach(rpl_dao_target_t, target, graph) { 01289 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.children) { 01290 if (!kill_transit) { 01291 goto kill_candidate; 01292 } 01293 /* Prefer to delete transits to already-connected targets. In a 01294 * simple scenario with one loop, for example: 01295 * 01296 * Root--->A--->B--->C--->D 01297 * ^------ / 01298 * 01299 * the initial pass will prune to: 01300 * 01301 * B--->C--->D 01302 * ^-------/ 01303 * 01304 * and only B will be marked "connected". D->B is the link to 01305 * kill to get everyone else connected. (Deleting B->C would 01306 * leave C unconnected. Deleting C->D would leave D unconnected.) 01307 * 01308 * With alternate paths like: 01309 * 01310 * /--------v 01311 * Root--->A--->B--->C--->D 01312 * ^------ / 01313 * 01314 * it would prune to 01315 * 01316 * B--->C--->D 01317 * ^------ / 01318 * 01319 * but this time both B and C would be connected. Deleting 01320 * either D->B or B->C would result in valid acyclic graphs, although 01321 * an optimal link might be lost. 01322 * 01323 * /--------v 01324 * Root--->A--->B--->C--->D 01325 * 01326 * /--------v 01327 * Root--->A--->B C--->D 01328 * ^-------/ 01329 */ 01330 if (!kill_transit->target->connected && transit->target->connected) { 01331 goto kill_candidate; 01332 } else if (kill_transit->target->connected && !transit->target->connected) { 01333 continue; 01334 } 01335 01336 /* Prefer to kill a higher-cost link */ 01337 if (kill_transit->cost < transit->cost) { 01338 goto kill_candidate; 01339 } else if (kill_transit->cost > transit->cost) { 01340 continue; 01341 } 01342 kill_candidate: 01343 kill_transit = transit; 01344 } 01345 } 01346 01347 /* Hopefully we killed found transit to a connected node to kill. */ 01348 /* If we didn't, it means we're on an isolated island, so we're dooomed anyway... */ 01349 01350 /* This removes it from our routing graph, but not from the master database */ 01351 ns_list_remove(&kill_transit->parent->info.root.children, kill_transit); 01352 rpl_downward_topo_sort_edge_removed(kill_transit, graph, top_nodes); 01353 } 01354 01355 /* Topologically sort instance->dao_targets - closest to border router placed at start */ 01356 static void rpl_downward_topo_sort(rpl_instance_t *instance) 01357 { 01358 if (instance->root_topo_sort_valid) { 01359 return; 01360 } 01361 01362 rpl_downward_link_transits_to_targets(instance); 01363 01364 rpl_dao_target_list_t sorted = NS_LIST_INIT(sorted); 01365 rpl_dao_target_list_t top_nodes = NS_LIST_INIT(top_nodes); 01366 01367 /* Find all the topmost targets - most should have been marked "connected", ie they 01368 * have exactly 1 link to the DODAG root. Some may be disconnected. */ 01369 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01370 if (target->info.root.cost == 0) { 01371 ns_list_remove(&instance->dao_targets, target); 01372 ns_list_add_to_end(&top_nodes, target); 01373 } 01374 } 01375 01376 retry_after_loop_break: 01377 ; 01378 /* Run the sort - targets are pulled off 'instance->dao_targets', and placed onto 'sorted' */ 01379 01380 rpl_dao_target_t *target; 01381 while ((target = ns_list_get_first(&top_nodes)) != NULL) { 01382 /* Take any topmost node, place on the end of the sorted list */ 01383 ns_list_remove(&top_nodes, target); 01384 ns_list_add_to_end(&sorted, target); 01385 01386 /* Decrement incoming link count on all children */ 01387 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.children) { 01388 rpl_downward_topo_sort_edge_removed(transit, &instance->dao_targets, &top_nodes); 01389 /* If this node is connected, the child is connected */ 01390 if (target->connected) { 01391 transit->target->connected = true; 01392 } 01393 01394 } 01395 } 01396 01397 if (!ns_list_is_empty(&instance->dao_targets)) { 01398 /* Didn't manage to empty the graph, so we have a loop - not a DAG */ 01399 do { 01400 rpl_downward_topo_sort_break_loop(&instance->dao_targets, &top_nodes); 01401 } while (ns_list_is_empty(&top_nodes)); 01402 goto retry_after_loop_break; 01403 } 01404 01405 /* Transfer sorted list back onto instance (dao_targets must be empty at this point) */ 01406 ns_list_concatenate(&instance->dao_targets, &sorted); 01407 instance->root_topo_sort_valid = true; 01408 } 01409 01410 /* Call when topo sort may have changed (or child links broken) - this invalidates everything */ 01411 static void rpl_downward_topo_sort_invalidate(rpl_instance_t *instance) 01412 { 01413 instance->root_topo_sort_valid = false; 01414 rpl_downward_paths_invalidate(instance); 01415 } 01416 01417 static void rpl_downward_update_path_cost_to_children(rpl_dao_root_transit_children_list_t *children, uint16_t parent_cost) 01418 { 01419 ns_list_foreach(rpl_dao_root_transit_t, transit, children) { 01420 rpl_dao_target_t *child = transit->target; 01421 uint16_t transit_cost = transit->cost; 01422 /* For directly-connected paths, modify for ETX or similar */ 01423 if (parent_cost == 0 && child->prefix_len == 128) { 01424 transit_cost = rpl_policy_modify_downward_cost_to_root_neighbour(child->instance->domain, child->interface_id, child->prefix, transit->cost); 01425 } 01426 if (child->info.root.cost > parent_cost + transit_cost) { 01427 /* Note new best cost to child, and make this transit the child's first/best */ 01428 child->info.root.cost = parent_cost + transit_cost; 01429 if (transit != ns_list_get_first(&child->info.root.transits)) { 01430 ns_list_remove(&child->info.root.transits, transit); 01431 ns_list_add_to_start(&child->info.root.transits, transit); 01432 } 01433 } 01434 } 01435 } 01436 01437 void rpl_downward_compute_paths(rpl_instance_t *instance) 01438 { 01439 if (instance->root_paths_valid) { 01440 return; 01441 } 01442 01443 /* First get targets into a topological sort - also breaks loops */ 01444 rpl_downward_topo_sort(instance); 01445 01446 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01447 target->info.root.cost = 0xFFFFFFFF; 01448 } 01449 01450 /* First process the direct root->child links, giving inital link costs */ 01451 rpl_downward_update_path_cost_to_children(&instance->root_children, 0); 01452 01453 /* Now process every node in turn */ 01454 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01455 /* Update connected flag - could be invalid due to node removal that didn't redo topo sort */ 01456 target->connected = target->info.root.cost != 0xFFFFFFFF; 01457 if (target->connected) { 01458 rpl_downward_update_path_cost_to_children(&target->info.root.children, target->info.root.cost); 01459 } 01460 } 01461 01462 instance->root_paths_valid = true; 01463 } 01464 01465 /* Called when path costs may have changed (but not topo sort) */ 01466 void rpl_downward_paths_invalidate(rpl_instance_t *instance) 01467 { 01468 instance->root_paths_valid = false; 01469 rpl_data_sr_invalidate(); 01470 } 01471 #endif // HAVE_RPL_ROOT 01472 01473 #ifdef HAVE_RPL_DAO_HANDLING 01474 bool rpl_instance_dao_received(rpl_instance_t *instance, const uint8_t src[16], int8_t interface_id, bool multicast, const uint8_t *opts, uint16_t opts_len, uint8_t *status) 01475 { 01476 rpl_dodag_t *dodag = rpl_instance_current_dodag(instance); 01477 if (!dodag) { 01478 return false; 01479 } 01480 if (multicast) { 01481 /* We don't handle multicast DAOs at all yet */ 01482 return false; 01483 } 01484 bool storing; 01485 switch (rpl_dodag_mop(dodag)) { 01486 default: 01487 case RPL_MODE_NO_DOWNWARD: 01488 return false; 01489 case RPL_MODE_NON_STORING: 01490 if (!rpl_dodag_am_root(dodag) || addr_is_ipv6_link_local(src)) { 01491 return false; 01492 } 01493 storing = false; 01494 break; 01495 case RPL_MODE_STORING: 01496 case RPL_MODE_STORING_MULTICAST: 01497 if (instance->current_rank == RPL_RANK_INFINITE || !addr_is_ipv6_link_local(src)) { 01498 return false; 01499 } 01500 storing = true; 01501 break; 01502 } 01503 01504 const uint8_t *start = opts, *end = opts + opts_len; 01505 01506 /* Basic format is ("group of targets", "group of transits"), repeated. 01507 * All the transits apply to all the preceding targets. So parsing is: 01508 * 1) When we see next target, and target group is closed, remember start of target group, open end. 01509 * 2) When we see a transit, mark end of target group if not already closed. 01510 * 3) Then for any transit, process the entire target group. 01511 */ 01512 const uint8_t *target_start = NULL, *target_end = opts; 01513 01514 bool new_info = false; 01515 *status = 0; 01516 01517 while (start < end) { 01518 switch (start[0]) { 01519 case RPL_TARGET_OPTION: 01520 if (target_end) { 01521 target_start = start; 01522 target_end = NULL; 01523 } 01524 break; 01525 case RPL_TRANSIT_OPTION: 01526 if (target_start) { 01527 if (!target_end) { 01528 target_end = start; 01529 } 01530 rpl_downward_process_targets_for_transit(dodag, storing, src, interface_id, target_start, target_end, start, &new_info, status); 01531 } else { 01532 tr_warn("Transit without Targets"); 01533 } 01534 break; 01535 case RPL_PAD1_OPTION: 01536 start++; 01537 continue; 01538 } 01539 start += 2 + start[1]; 01540 } 01541 01542 if (new_info && storing) { 01543 rpl_instance_dao_trigger(instance, 0); 01544 } 01545 01546 return true; 01547 } 01548 #endif // HAVE_RPL_DAO_HANDLING 01549 01550 void rpl_instance_dao_acked(rpl_instance_t *instance, const uint8_t src[16], int8_t interface_id, uint8_t dao_sequence, uint8_t status) 01551 { 01552 if (!instance->dao_in_transit || dao_sequence != instance->dao_sequence_in_transit) { 01553 return; 01554 } 01555 01556 if (src) { 01557 ipv6_neighbour_reachability_confirmation(src, interface_id); 01558 } 01559 01560 bool retry = false; 01561 if (status == 0) { 01562 tr_debug("DAO-ACK RX"); /* Some tests rely on this debug */ 01563 } else { 01564 if (src) { 01565 tr_warn("DAO rejection from %s: status=%d", trace_ipv6(src), status); 01566 } else { 01567 tr_warn("DAO timeout"); 01568 retry = true; 01569 } 01570 } 01571 01572 rpl_dodag_t *dodag = rpl_instance_current_dodag(instance); 01573 const rpl_dodag_conf_t *conf = dodag ? rpl_dodag_get_config(dodag) : NULL; 01574 instance->dao_in_transit = false; 01575 instance->dao_retry_timer = 0; 01576 if (!retry) { 01577 instance->dao_attempt = 0; 01578 } 01579 01580 bool more_to_do = false; 01581 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01582 if (target->root) { 01583 continue; 01584 } 01585 tr_debug("tgt %s - pc %02x, assigned %02x, assigning %02x, life %02x, rfr %"PRIu32, 01586 trace_ipv6_prefix(target->prefix, target->prefix_len), 01587 target->path_control, 01588 target->info.non_root.pc_assigned, 01589 target->info.non_root.pc_assigning, 01590 target->info.non_root.path_lifetime, 01591 target->info.non_root.refresh_timer); 01592 target->info.non_root.pc_assigning &= target->path_control; 01593 if (target->info.non_root.pc_assigning) { 01594 if (!retry) { 01595 target->info.non_root.pc_assigned |= target->info.non_root.pc_assigning; 01596 } else { 01597 target->info.non_root.pc_to_retry |= target->info.non_root.pc_assigning; 01598 } 01599 target->info.non_root.pc_assigning = 0; 01600 } 01601 target->info.non_root.pc_assigned &= target->path_control; 01602 if (target->info.non_root.pc_assigned != target->path_control) { 01603 more_to_do = true; 01604 } else { 01605 if (target->published && target->info.non_root.refresh_timer == 0) { 01606 uint32_t t; 01607 if (conf && target->info.non_root.path_lifetime != 0xFF) { 01608 t = (uint32_t) target->info.non_root.path_lifetime * conf->lifetime_unit; 01609 /* Refresh between 1/2 and 3/4 of lifetime */ 01610 t = randLIB_randomise_base(t, 0x4000, 0x6000); 01611 } else { 01612 t = 0xFFFFFFFF; 01613 } 01614 #ifdef MINIMUM_DAO_TARGET_REFRESH 01615 if (t > MINIMUM_DAO_TARGET_REFRESH) { 01616 t = randLIB_randomise_base(MINIMUM_DAO_TARGET_REFRESH, 0x7333, 0x8CCD); /* +/- 10% */ 01617 } 01618 #endif 01619 target->info.non_root.refresh_timer = t; 01620 tr_debug("set rfr to %"PRIu32, t); 01621 } 01622 } 01623 } 01624 01625 if (more_to_do) { 01626 rpl_instance_dao_trigger(instance, 1); 01627 } else { 01628 rpl_control_event(instance->domain, RPL_EVENT_DAO_DONE); 01629 } 01630 } 01631 01632 void rpl_instance_dao_request(struct rpl_instance *instance, struct rpl_neighbour *neighbour) 01633 { 01634 uint8_t pc_mask = neighbour ? neighbour->dao_path_control : 0xFF; 01635 01636 if (!pc_mask) { 01637 return; 01638 } 01639 01640 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01641 if (!target->root) { 01642 target->info.non_root.pc_assigned &= ~pc_mask; 01643 target->info.non_root.pc_to_retry &= ~pc_mask; 01644 } 01645 } 01646 01647 rpl_instance_dao_trigger(instance, 0); 01648 } 01649 01650 01651 void rpl_downward_dao_slow_timer(rpl_instance_t *instance, uint16_t seconds) 01652 { 01653 if (!instance) { 01654 return; 01655 } 01656 /* Process lifetimes on all targets for expiry */ 01657 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01658 if (target->lifetime == 0xFFFFFFFF) { 01659 continue; 01660 } 01661 if (target->lifetime > seconds) { 01662 target->lifetime -= seconds; 01663 continue; 01664 } 01665 rpl_delete_dao_target(instance, target); 01666 } 01667 01668 /* Perform target auto-refresh for published targets */ 01669 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01670 if (!target->published) { 01671 continue; 01672 } 01673 if (target->info.non_root.refresh_timer == 0xFFFFFFFF || target->info.non_root.refresh_timer == 0) { 01674 continue; 01675 } 01676 if (target->info.non_root.refresh_timer > seconds) { 01677 target->info.non_root.refresh_timer -= seconds; 01678 continue; 01679 } 01680 /* Refresh the DAO target */ 01681 target->info.non_root.refresh_timer = 0; 01682 rpl_downward_target_refresh(target); 01683 rpl_instance_dao_trigger(instance, 0); 01684 } 01685 } 01686 01687 void rpl_downward_dao_timer(rpl_instance_t *instance, uint16_t ticks) 01688 { 01689 if (instance->dao_retry_timer) { 01690 if (instance->dao_retry_timer > ticks) { 01691 instance->dao_retry_timer -= ticks; 01692 } else { 01693 instance->dao_retry_timer = 0; 01694 if (!instance->requested_dao_ack) { 01695 /* Act as if ACK arrived at first retry point (gives them 01696 * time to send a failure). 01697 */ 01698 rpl_instance_dao_acked(instance, NULL, -1, instance->dao_sequence_in_transit, 0); 01699 } else { 01700 rpl_instance_dao_acked(instance, NULL, -1, instance->dao_sequence_in_transit, 0xFF); 01701 } 01702 } 01703 } 01704 01705 if (instance->delay_dao_timer) { 01706 if (instance->delay_dao_timer > ticks) { 01707 instance->delay_dao_timer -= ticks; 01708 } else { 01709 instance->delay_dao_timer = 0; 01710 rpl_instance_send_dao_update(instance); 01711 } 01712 } 01713 } 01714 01715 void rpl_downward_print_instance(rpl_instance_t *instance, route_print_fn_t *print_fn) 01716 { 01717 if (ns_list_is_empty(&instance->dao_targets)) { 01718 return; 01719 } 01720 print_fn("DAO Targets:"); 01721 if (rpl_instance_am_root(instance)) { 01722 rpl_downward_compute_paths(instance); 01723 } 01724 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01725 01726 char str_buf[44]; 01727 ip6_prefix_tos(target->prefix, target->prefix_len, str_buf); 01728 #ifdef HAVE_RPL_ROOT 01729 if (target->root) { 01730 print_fn(" %-40s %02x seq=%d%s cost=%"PRIu32"%s%s%s", 01731 str_buf, 01732 target->path_control, target->path_sequence, target->need_seq_inc ? "+" : "", 01733 target->info.root.cost, 01734 target->published ? " (pub)" : "", 01735 target->external ? " (E)" : "", 01736 target->connected ? "" : " (disconnected)"); 01737 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01738 // Reuse str_buf as it's no longer needed and it's large enough for ROUTE_PRINT_ADDR_STR_FORMAT. 01739 print_fn(" ->%-36s %02x cost=%"PRIu16, ROUTE_PRINT_ADDR_STR_FORMAT(str_buf, transit->transit), transit->path_control, transit->cost); 01740 } 01741 } else 01742 #endif 01743 { 01744 print_fn(" %-40s %02x seq=%d%s%s%s", 01745 str_buf, 01746 target->path_control, target->path_sequence, target->need_seq_inc ? "+" : "", 01747 target->published ? " (pub)" : "", 01748 target->external ? " (E)" : ""); 01749 } 01750 } 01751 } 01752 01753 rpl_dao_target_t *rpl_instance_get_active_target_confirmation(rpl_instance_t *instance) 01754 { 01755 ns_list_foreach_safe(rpl_dao_target_t, n, &instance->dao_targets) { 01756 if (!n->active_confirmation_state) { 01757 continue; 01758 } 01759 return n; 01760 01761 } 01762 return NULL; 01763 } 01764 01765 static rpl_neighbour_t *rpl_instance_get_unconfirmed_parent_info(rpl_instance_t *instance) 01766 { 01767 ns_list_foreach_safe(rpl_neighbour_t, n, &instance->candidate_neighbours) { 01768 if (n->dao_path_control != 0 && !n->confirmed) { 01769 return n; 01770 } 01771 01772 } 01773 return NULL; 01774 } 01775 01776 static bool rpl_instance_push_address_registration(protocol_interface_info_entry_t *interface, rpl_neighbour_t *neighbour, if_address_entry_t *addr) 01777 { 01778 aro_t aro; 01779 01780 aro.status = ARO_SUCCESS; 01781 aro.present = true; 01782 aro.lifetime = (addr->valid_lifetime / 60) + 1; 01783 memcpy(aro.eui64, interface->mac, 8); 01784 01785 buffer_t *buf = icmpv6_build_ns(interface, neighbour->ll_address, addr->address, true, false, &aro); 01786 if (!buf) { 01787 return false; 01788 } 01789 tr_debug("Send ARO %s to %s", trace_ipv6(addr->address), trace_ipv6(neighbour->ll_address)); 01790 protocol_push(buf); 01791 return true; 01792 } 01793 static if_address_entry_t *rpl_interface_addr_get(protocol_interface_info_entry_t *interface, const uint8_t addr[16]) 01794 { 01795 ns_list_foreach(if_address_entry_t, entry, &interface->ip_addresses) { 01796 if (memcmp(entry->address, addr, 16) == 0) { 01797 return entry; 01798 } 01799 } 01800 return NULL; 01801 } 01802 01803 static void rpl_instance_address_registration_cancel(rpl_instance_t *instance) 01804 { 01805 ns_list_foreach_safe(rpl_dao_target_t, n, &instance->dao_targets) { 01806 n->active_confirmation_state = false; 01807 n->trig_confirmation_state = false; 01808 n->response_wait_time = 0; 01809 } 01810 01811 instance->wait_response = NULL; 01812 instance->pending_neighbour_confirmation = false; 01813 instance->delay_dao_timer = 0; 01814 } 01815 01816 void rpl_instance_parent_address_reg_timer_update(rpl_instance_t *instance, uint16_t seconds) 01817 { 01818 if (!instance->pending_neighbour_confirmation) { 01819 return; //No need validate any confirmation 01820 } 01821 01822 //Verify that we have selected parent and it have a dao path control 01823 if (!rpl_instance_parent_selection_ready(instance)) { 01824 rpl_instance_address_registration_cancel(instance); 01825 return; 01826 } 01827 01828 //Get Pendig active target 01829 rpl_dao_target_t *dao_target = rpl_instance_get_active_target_confirmation(instance); 01830 if (!dao_target) { 01831 dao_target = rpl_instance_get_pending_target_confirmation(instance); 01832 if (!dao_target) { 01833 instance->pending_neighbour_confirmation = false; 01834 return; 01835 } 01836 01837 tr_debug("Register Address to parent %s", trace_ipv6(dao_target->prefix)); 01838 } 01839 01840 if (instance->wait_response) { 01841 if (seconds < dao_target->response_wait_time) { 01842 //Must Wait response time untill finish 01843 dao_target->response_wait_time -= seconds; 01844 return; 01845 } 01846 dao_target->response_wait_time = 0; 01847 instance->wait_response = NULL; 01848 } 01849 01850 //Get Next Parent for confirmation 01851 rpl_neighbour_t *neighbour = rpl_instance_get_unconfirmed_parent_info(instance); 01852 if (!neighbour) { 01853 dao_target->active_confirmation_state = false; 01854 return; 01855 } 01856 01857 //Get address and buffer 01858 protocol_interface_info_entry_t *interface = protocol_stack_interface_info_get_by_id(neighbour->interface_id); 01859 if (!interface) { 01860 rpl_instance_address_registration_cancel(instance); 01861 return; 01862 } 01863 01864 if_address_entry_t *address = rpl_interface_addr_get(interface, dao_target->prefix); 01865 if (!address) { 01866 rpl_instance_address_registration_cancel(instance); 01867 return; 01868 } 01869 01870 01871 if (rpl_instance_push_address_registration(interface, neighbour, address)) { 01872 instance->wait_response = neighbour; 01873 dao_target->response_wait_time = 5; 01874 } 01875 01876 } 01877 01878 void rpl_instance_address_registration_done(protocol_interface_info_entry_t *interface, rpl_instance_t *instance, rpl_neighbour_t *neighbour, uint8_t status) 01879 { 01880 01881 if (!instance->pending_neighbour_confirmation) { 01882 return; 01883 } 01884 01885 rpl_dao_target_t *dao_target = rpl_instance_get_active_target_confirmation(instance); 01886 if (!dao_target || instance->wait_response != neighbour) { 01887 return; 01888 } 01889 01890 tr_debug("Address %s register to %s", trace_ipv6(dao_target->prefix), trace_ipv6(neighbour->ll_address)); 01891 01892 if (status == SOCKET_TX_DONE) { 01893 /* State_timer is 1/10 s. Set renewal to 75-85% of lifetime */ 01894 if_address_entry_t *address = rpl_interface_addr_get(interface, dao_target->prefix); 01895 if (address && address->source != ADDR_SOURCE_DHCP) { 01896 address->state_timer = (address->preferred_lifetime * randLIB_get_random_in_range(75, 85) / 10); 01897 } 01898 neighbour->confirmed = true; 01899 dao_target->response_wait_time = 6; 01900 } else { 01901 tr_error("Address registration failed"); 01902 rpl_delete_neighbour(instance, neighbour); 01903 rpl_instance_address_registration_cancel(instance); 01904 } 01905 } 01906 01907 #endif /* HAVE_RPL */
Generated on Tue Jul 12 2022 13:54:48 by
1.7.2