takashi kadono
/
Nucleo_446
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.
Embed:
(wiki syntax)
Show/hide line numbers
rpl_downward.c
00001 /* 00002 * Copyright (c) 2015-2018, 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 void rpl_downward_neighbour_gone(rpl_instance_t *instance, rpl_neighbour_t *neighbour) 00184 { 00185 if (neighbour->dao_path_control == 0) { 00186 return; 00187 } 00188 neighbour->old_dao_path_control = neighbour->dao_path_control; 00189 neighbour->dao_path_control = 0; 00190 rpl_downward_process_dao_parent_changes(instance); 00191 } 00192 00193 void rpl_downward_process_dao_parent_changes(rpl_instance_t *instance) 00194 { 00195 uint8_t mop = rpl_instance_mop(instance); 00196 bool storing; 00197 00198 switch (mop) { 00199 case RPL_MODE_NON_STORING: 00200 storing = false; 00201 break; 00202 case RPL_MODE_STORING: 00203 case RPL_MODE_STORING_MULTICAST: 00204 storing = true; 00205 break; 00206 default: 00207 return; 00208 } 00209 00210 bool bits_removed = false; 00211 uint8_t bits_added = 0; 00212 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00213 if (neighbour->old_dao_path_control != neighbour->dao_path_control) { 00214 if (neighbour->old_dao_path_control &~ neighbour->dao_path_control) { 00215 bits_removed = true; 00216 break; 00217 } else { 00218 /* May as well resend all bits for this parent, not just new */ 00219 bits_added |= neighbour->dao_path_control; 00220 } 00221 } 00222 } 00223 tr_debug("removed=%x, added=%x", bits_removed, bits_added); 00224 if (!(bits_removed || bits_added)) { 00225 return; 00226 } 00227 00228 if (storing) { 00229 /* XXX more complicated - No-Paths to people losing stuff, etc. 00230 * Need to think a bit about what each parent would have had. 00231 * Different handling for stuff we own and stuff we don't. Can 00232 * probably actually unify somewhat, but needs thought. 00233 */ 00234 } else { 00235 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00236 if (target->published && target->own) { 00237 if (bits_removed) { 00238 /* Simple - just increment Path Sequence and trigger DAO to root */ 00239 rpl_downward_target_refresh(target); 00240 } else { 00241 /* Make sure we send the newly-added bits (would previously have been assigned to no-one) */ 00242 target->info.non_root.pc_assigned &= ~bits_added; 00243 } 00244 } 00245 } 00246 rpl_instance_dao_trigger(instance, 0); 00247 } 00248 } 00249 00250 rpl_dao_target_t *rpl_create_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len, bool root) 00251 { 00252 rpl_dao_target_t *target = rpl_alloc(sizeof(rpl_dao_target_t)); 00253 if (!target) { 00254 tr_warn("RPL DAO overflow (target=%s)", trace_ipv6_prefix(prefix, prefix_len)); 00255 return NULL; 00256 } 00257 memset(target, 0, sizeof *target); 00258 bitcopy0(target->prefix, prefix, prefix_len); 00259 target->instance = instance; 00260 target->prefix_len = prefix_len; 00261 target->path_sequence = rpl_seq_init(); 00262 target->root = root; 00263 #ifdef HAVE_RPL_ROOT 00264 if (root) { 00265 ns_list_init(&target->info.root.transits); 00266 } 00267 rpl_downward_topo_sort_invalidate(instance); 00268 #endif 00269 00270 ns_list_add_to_end(&instance->dao_targets, target); 00271 return target; 00272 } 00273 00274 void rpl_delete_dao_target(rpl_instance_t *instance, rpl_dao_target_t *target) 00275 { 00276 /* XXX For each notified parent, send a No-Path DAO */ 00277 00278 /* TODO - should send a No-Path to root */ 00279 00280 ns_list_remove(&instance->dao_targets, target); 00281 00282 #ifdef HAVE_RPL_ROOT 00283 if (target->root) { 00284 ns_list_foreach_safe(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 00285 ns_list_remove(&target->info.root.transits, transit); 00286 rpl_free(transit, sizeof *transit); 00287 } 00288 ipv6_route_table_remove_info(-1, ROUTE_RPL_DAO_SR, target); 00289 rpl_downward_topo_sort_invalidate(target->instance); 00290 } 00291 #endif 00292 rpl_free(target, sizeof *target); 00293 } 00294 00295 rpl_dao_target_t *rpl_instance_lookup_published_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00296 { 00297 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00298 if (target->published && target->prefix_len == prefix_len && 00299 bitsequal(target->prefix, prefix, prefix_len)) { 00300 return target; 00301 } 00302 } 00303 return NULL; 00304 } 00305 00306 rpl_dao_target_t *rpl_instance_lookup_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00307 { 00308 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00309 if (target->prefix_len == prefix_len && 00310 bitsequal(target->prefix, prefix, prefix_len)) { 00311 return target; 00312 } 00313 } 00314 return NULL; 00315 } 00316 00317 rpl_dao_target_t *rpl_instance_match_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00318 { 00319 rpl_dao_target_t *longest = NULL; 00320 int_fast16_t longest_len = -1; 00321 00322 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00323 if (target->prefix_len >= longest_len && target->prefix_len <= prefix_len && 00324 bitsequal(target->prefix, prefix, target->prefix_len)) { 00325 longest = target; 00326 longest_len = target->prefix_len; 00327 if (longest_len == 128) { 00328 break; 00329 } 00330 } 00331 } 00332 return longest; 00333 } 00334 void rpl_instance_delete_published_dao_target(rpl_instance_t *instance, const uint8_t *prefix, uint8_t prefix_len) 00335 { 00336 rpl_dao_target_t *target = rpl_instance_lookup_published_dao_target(instance, prefix, prefix_len); 00337 if (target) { 00338 rpl_delete_dao_target(instance, target); 00339 } 00340 } 00341 00342 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) 00343 { 00344 rpl_dao_target_t *target = rpl_instance_lookup_published_dao_target(instance, prefix, prefix_len); 00345 if (target) { 00346 target->lifetime = valid_lifetime; 00347 if (!own) { 00348 /* For non-owned targets, publish triggers a refresh */ 00349 rpl_downward_target_refresh(target); 00350 rpl_instance_dao_trigger(instance, 0); 00351 } 00352 return; 00353 } 00354 target = rpl_create_dao_target(instance, prefix, prefix_len, false); 00355 if (!target) { 00356 tr_warn("Failed to publish DAO target %s", trace_ipv6_prefix(prefix, prefix_len)); 00357 return; 00358 } 00359 target->interface_id = -1; 00360 target->published = true; 00361 target->own = own; 00362 target->external = !own; 00363 target->lifetime = valid_lifetime; 00364 if (own) { 00365 target->info.non_root.refresh_timer = 0; /* Auto-refresh */ 00366 } else { 00367 target->info.non_root.refresh_timer = 0xFFFFFFFF; /* Do not refresh - require republishing */ 00368 } 00369 target->descriptor_present = want_descriptor; 00370 target->descriptor = descriptor; 00371 target->path_control = 0xFF; /* Use as much path control as we can (PCS limits) */ 00372 /* Path lifetime left as 0 for now - will be filled in on transmission, along with refresh timer */ 00373 rpl_instance_dao_trigger(instance, 0); 00374 } 00375 00376 void rpl_instance_dao_trigger(rpl_instance_t *instance, uint16_t delay) 00377 { 00378 if (delay == 0) { 00379 delay = randLIB_randomise_base(DEFAULT_DAO_DELAY, 0x4000, 0xC000); 00380 } 00381 if (instance->delay_dao_timer == 0 || instance->delay_dao_timer > delay) { 00382 instance->delay_dao_timer = delay; 00383 tr_debug("DAO trigger %" PRIu16, delay); 00384 } 00385 } 00386 00387 /* 00388 * 0 1 2 3 00389 * 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 00390 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00391 * | Type = 0x05 | Option Length | Flags | Prefix Length | 00392 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00393 * | | 00394 * + + 00395 * | Target Prefix (Variable Length) | 00396 * . . 00397 * . . 00398 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00399 * 00400 * Figure 25: Format of the RPL Target Option 00401 * 00402 * 0 1 2 3 00403 * 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 00404 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00405 * | Type = 0x09 |Opt Length = 4 | Descriptor 00406 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00407 * Descriptor (cont.) | 00408 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00409 * 00410 * Figure 30: Format of the RPL Target Descriptor Option 00411 */ 00412 static uint8_t *rpl_downward_write_target(uint8_t *ptr, rpl_dao_target_t *target) 00413 { 00414 uint8_t byte_len = (target->prefix_len + 7u) / 8u; 00415 *ptr++ = RPL_TARGET_OPTION; 00416 *ptr++ = 2 + byte_len; 00417 *ptr++ = 0; // flags 00418 *ptr++ = target->prefix_len; 00419 bitcopy0(ptr, target->prefix, target->prefix_len); 00420 ptr += byte_len; 00421 00422 if (target->descriptor_present) { 00423 *ptr++ = RPL_TARGET_DESC_OPTION; 00424 *ptr++ = 4; 00425 ptr = common_write_32_bit(target->descriptor, ptr); 00426 } 00427 00428 return ptr; 00429 } 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 = 0x06 | Option Length |E| Flags | Path Control | 00435 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00436 * | Path Sequence | Path Lifetime | | 00437 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 00438 * | | 00439 * + + 00440 * | | 00441 * + Parent Address* + 00442 * | | 00443 * + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00444 * | | 00445 * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 00446 * 00447 * Figure 26: Format of the Transit Information Option 00448 * 00449 */ 00450 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) 00451 { 00452 *ptr++ = RPL_TRANSIT_OPTION; 00453 *ptr++ = parent ? 16 + 4 : 4; 00454 *ptr++ = target->external ? TRANSIT_FLAG_EXTERNAL : 0; 00455 *ptr++ = path_control; 00456 *ptr++ = target->path_sequence; 00457 *ptr++ = no_path ? 0 : target->info.non_root.path_lifetime; 00458 if (parent) { 00459 ptr = (uint8_t *) memcpy(ptr, parent, 16) + 16; 00460 } 00461 00462 return ptr; 00463 } 00464 00465 static bool rpl_instance_clear_target_pc_to_retry(rpl_instance_t *instance) 00466 { 00467 bool had_retry = false; 00468 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00469 if (!target->root && target->info.non_root.pc_to_retry) { 00470 target->info.non_root.pc_to_retry = 0; 00471 had_retry = true; 00472 } 00473 } 00474 00475 return had_retry; 00476 } 00477 00478 /* Find a target that needs updating. For storing mode, after first is found, 00479 * subsequent must be for the same parent. 00480 */ 00481 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) 00482 { 00483 retry: 00484 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00485 if (target->root || target == t1) { 00486 continue; 00487 } 00488 00489 /* Check if this target has any unassigned path control bits */ 00490 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); 00491 if (!unassigned_pc) { 00492 continue; 00493 } 00494 00495 /* If we are looking for a follow-up target to share transit, transit data must match */ 00496 if (t1) { 00497 uint8_t target_seq = target->path_sequence; 00498 if (target->need_seq_inc) { 00499 target_seq = rpl_seq_inc(target_seq); 00500 } 00501 if (target->external != t1->external || target->own != t1->own || 00502 target_seq != t1->path_sequence || 00503 target->info.non_root.path_lifetime != t1->info.non_root.path_lifetime) { 00504 continue; 00505 } 00506 } 00507 00508 /* unassigned_pc is the total path control needing assignment */ 00509 if (!storing) { 00510 /* In non-storing mode, any number of targets+transits can be output to root in 1 DAO */ 00511 /* Leave unassigned_pc as the entire path control across all parents */ 00512 } else if (*parent == NULL) { 00513 /* In storing mode, need to choose a parent, if we haven't already */ 00514 /* This is the very first target for the DAO - we now choose a parent that wants 00515 * the bits, and output that parent's path control so we use it for future targets. 00516 */ 00517 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00518 if (neighbour->dao_path_control & unassigned_pc) { 00519 unassigned_pc &= neighbour->dao_path_control; 00520 *path_control = unassigned_pc; 00521 *parent = neighbour; 00522 return target; 00523 } 00524 } 00525 } else { 00526 /* This is not the first target - we must be picking subsequent 00527 * targets with unassigned bits for the parent we chose last time. 00528 */ 00529 unassigned_pc &= (*parent)->dao_path_control; 00530 if (!unassigned_pc) { 00531 continue; 00532 } 00533 } 00534 00535 /* If looking for a follow-up target, final path control must match */ 00536 if (t1) { 00537 if (unassigned_pc != *path_control) { 00538 continue; 00539 } 00540 } else { 00541 *path_control = unassigned_pc; 00542 } 00543 return target; 00544 } 00545 00546 if (!t1) { 00547 /* If found nothing on initial search, it would appear we're done. However, 00548 * we were skipping "to_retry" assignments. Clear to_retry flags, and if 00549 * there were any, retry. We currently retry indefinitely (but with 00550 * exponential backoff). 00551 */ 00552 if (rpl_instance_clear_target_pc_to_retry(instance)) { 00553 if (instance->dao_attempt < 255) { 00554 ++instance->dao_attempt; 00555 } 00556 tr_warn("DAO retry, attempt %d", instance->dao_attempt); 00557 goto retry; 00558 } 00559 } 00560 return NULL; 00561 } 00562 00563 static void rpl_downward_reset_assigning(rpl_instance_t *instance, uint8_t pcs_mask) 00564 { 00565 uint8_t parent_mask = 0; 00566 /* Check to see if we're short of parent mask coverage. If so, remove bits from the mask */ 00567 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00568 parent_mask |= neighbour->dao_path_control; 00569 } 00570 pcs_mask &= parent_mask; 00571 00572 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 00573 target->info.non_root.pc_assigning = 0; 00574 /* For ease of processing, we allow target path control to have bits 00575 * beyond the mask. In this pass, we quietly mark those bits as 00576 * "assigned", as if we've sent them to an invisible parent. 00577 */ 00578 target->info.non_root.pc_assigned |= (target->path_control & ~pcs_mask); 00579 target->info.non_root.pc_to_retry &= pcs_mask; 00580 } 00581 } 00582 00583 00584 void rpl_instance_send_address_registration(protocol_interface_info_entry_t *interface, rpl_instance_t *instance, if_address_entry_t *addr) 00585 { 00586 aro_t aro; 00587 buffer_t *buf; 00588 00589 aro.status = ARO_SUCCESS; 00590 aro.present = true; 00591 aro.lifetime = addr->preferred_lifetime; 00592 memcpy(aro.eui64, interface->mac, 8); 00593 00594 // go through neighbour list, and send to all assigned parents. 00595 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00596 if (neighbour->dao_path_control) { 00597 tr_debug("Send ARO %s to %s", trace_ipv6(addr->address), trace_ipv6(neighbour->ll_address)); 00598 buf = icmpv6_build_ns(interface, neighbour->ll_address, addr->address, true, false, &aro); 00599 addr->addr_reg_pend |= neighbour->dao_path_control; 00600 protocol_push(buf); 00601 } else { 00602 tr_debug("Skip ARO to %s - no pc", trace_ipv6(neighbour->ll_address)); 00603 } 00604 } 00605 } 00606 00607 bool rpl_instance_address_registration_done(protocol_interface_info_entry_t *interface, rpl_instance_t *instance, if_address_entry_t *addr, uint8_t status) 00608 { 00609 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00610 // Check path control mask 00611 if (!(addr->addr_reg_pend & neighbour->dao_path_control)) { 00612 continue; 00613 } 00614 00615 tr_debug("Address %s register to %s", trace_ipv6(addr->address), trace_ipv6(neighbour->ll_address)); 00616 00617 /* Clear pending flag */ 00618 addr->addr_reg_pend &= ~neighbour->dao_path_control; 00619 00620 if (status == SOCKET_TX_DONE) { 00621 addr->addr_reg_done |= neighbour->dao_path_control; 00622 /* State_timer is 1/10 s. Set renewal to 75-85% of lifetime */ 00623 addr->state_timer = (addr->preferred_lifetime * randLIB_get_random_in_range(75, 85) / 10); 00624 } else { 00625 tr_error("Address registration failed"); 00626 } 00627 00628 /* If that was last one to reply, send next one. */ 00629 if (!addr->addr_reg_pend) { 00630 rpl_control_register_address(interface, NULL); 00631 } 00632 00633 return true; 00634 } 00635 00636 return false; 00637 } 00638 00639 /* We are optimised for sending updates to existing targets to current parents; 00640 * we track the state of what information DAO parents have, and manage the 00641 * updates together with message coalescing and ack tracking. 00642 * 00643 * No-Paths are handled separately, and not tracked - we spit out No-Paths 00644 * at the moment targets or parents are deleted, 1 attempt only. 00645 * 00646 * This function only has to deals with updating our active state. 00647 */ 00648 void rpl_instance_send_dao_update(rpl_instance_t *instance) 00649 { 00650 instance->delay_dao_timer = 0; 00651 00652 rpl_dodag_t *dodag = rpl_instance_current_dodag(instance); 00653 if (!dodag || rpl_dodag_am_root(dodag)) { 00654 return; 00655 } 00656 00657 uint8_t mop = rpl_dodag_mop(dodag); 00658 bool storing; 00659 00660 switch (mop) { 00661 case RPL_MODE_NON_STORING: 00662 storing = false; 00663 break; 00664 case RPL_MODE_STORING: 00665 case RPL_MODE_STORING_MULTICAST: 00666 storing = true; 00667 break; 00668 default: 00669 return; 00670 } 00671 00672 if (instance->dao_in_transit) { 00673 // Force current DAO timeout to be cut short, then 00674 // when it times out, it will re-evaluate the situation, 00675 // and come back back here. 00676 uint16_t delay = rpl_policy_initial_dao_ack_wait(instance->domain, mop); 00677 if (instance->dao_retry_timer > delay) { 00678 instance->dao_retry_timer = delay; 00679 } 00680 return; 00681 } 00682 00683 00684 /* Which parent this DAO will be for if storing */ 00685 rpl_neighbour_t *parent = NULL; 00686 00687 /* Need our address to publish DAOs of attached hosts */ 00688 const uint8_t *our_addr = NULL; 00689 if (!storing) { 00690 ns_list_foreach(rpl_dao_target_t, t, &instance->dao_targets) { 00691 if (t->published && t->own && t->prefix_len == 128) { 00692 our_addr = t->prefix; 00693 break; 00694 } 00695 } 00696 } 00697 00698 /* To avoid packet overflow, we set a fairly conservative limit of how 00699 * many targets to put in a message. 00700 * 00701 * For storing mode, format is: 00702 * Base (4-20) 00703 * //Target (4-20, typically 20) 00704 * |\Descriptor (0-6) 00705 * |(^Repeat if more targets with same transit info) 00706 * \ Transit (6) 00707 * (^ Repeat if more targets for same parent, with different transit info) 00708 * 00709 * For non-storing mode, format is: 00710 * Base 00711 * //Target (4-20, typically 20) 00712 * |\Descriptor (0-6) 00713 * |(^Repeat if more targets with same transit info) 00714 * | Transit for parent 1 (22) 00715 * | Transit for parent 2 (22) 00716 * \ Transit... (22) (max 8 = 176 per target set) 00717 * (^ Repeat if more targets with different transit info/parents) 00718 */ 00719 00720 00721 uint8_t *opts = ns_dyn_mem_temporary_alloc(1280); 00722 if (!opts) { 00723 rpl_instance_dao_trigger(instance, 0); 00724 return; 00725 } 00726 uint8_t *ptr = opts; 00727 00728 rpl_downward_reset_assigning(instance, PCSMASK(dodag->config.path_control_size)); 00729 00730 ns_list_foreach(rpl_dao_target_t, t, &instance->dao_targets) { 00731 /* Self-published targets can defer path lifetime choice */ 00732 if (t->info.non_root.path_lifetime == 0) { 00733 uint32_t lifetime = t->lifetime; 00734 const rpl_dodag_conf_t *conf = rpl_dodag_get_config(dodag); 00735 uint16_t unit = conf->lifetime_unit; 00736 uint8_t def = conf->default_lifetime; 00737 if (lifetime != 0xFFFFFFFF) { 00738 lifetime = (lifetime + unit - 1) / unit; 00739 } 00740 if (lifetime > def) { 00741 lifetime = def; 00742 } 00743 t->info.non_root.path_lifetime = lifetime; 00744 } 00745 } 00746 00747 00748 /* We keep going until size exceeds 768. This gives plenty of slop to fit 00749 * in a 1280-byte packet. 00750 */ 00751 while (ptr < opts + 768) { 00752 uint8_t path_control; 00753 /* Find a target that needs an update - after the first, it must be for the current parent */ 00754 rpl_dao_target_t *target = rpl_instance_choose_target_to_assign(instance, storing, &parent, &path_control, NULL); 00755 if (!target) { 00756 break; 00757 } 00758 00759 /* Stupid error case - can't publish non-owned addresses if we don't know our own address */ 00760 if (!storing && !target->own && !our_addr) { 00761 target->info.non_root.pc_assigned |= path_control; 00762 continue; 00763 } 00764 00765 if (target->need_seq_inc) { 00766 target->path_sequence = rpl_seq_inc(target->path_sequence); 00767 target->need_seq_inc = false; 00768 } 00769 00770 ptr = rpl_downward_write_target(ptr, target); 00771 target->info.non_root.pc_assigning = path_control; 00772 00773 /* Then find more targets with the same transit info - can compress */ 00774 while (ptr < opts + 768) { 00775 rpl_dao_target_t *t2 = rpl_instance_choose_target_to_assign(instance, storing, &parent, &path_control, target); 00776 if (!t2) { 00777 break; 00778 } 00779 t2->path_sequence = target->path_sequence; 00780 t2->need_seq_inc = false; 00781 t2->info.non_root.pc_assigning = path_control; 00782 ptr = rpl_downward_write_target(ptr, t2); 00783 } 00784 00785 /* Then output the transit information for the original target */ 00786 if (storing) { 00787 /* Just one transit info */ 00788 ptr = rpl_downward_write_transit(ptr, target, path_control, NULL, false); 00789 } else if (target->own) { 00790 /* One transit info for each DAO parent */ 00791 ns_list_foreach(rpl_neighbour_t, neighbour, &instance->candidate_neighbours) { 00792 if (neighbour->dao_path_control & path_control) { 00793 ptr = rpl_downward_write_transit(ptr, target, neighbour->dao_path_control & path_control, neighbour->global_address, false); 00794 } 00795 } 00796 } else { 00797 /* Attached host - single transit is us */ 00798 ptr = rpl_downward_write_transit(ptr, target, path_control, our_addr, false); 00799 } 00800 } 00801 00802 if (ptr == opts) { 00803 /* Had nothing... */ 00804 ns_dyn_mem_free(opts); 00805 return; 00806 } 00807 00808 const uint8_t *dst; 00809 protocol_interface_info_entry_t *cur; 00810 if (storing) { 00811 dst = parent->ll_address; 00812 cur = protocol_stack_interface_info_get_by_id(parent->interface_id); 00813 } else { 00814 dst = dodag->id; 00815 cur = NULL; 00816 } 00817 00818 bool need_ack = rpl_control_transmit_dao(instance->domain, cur, instance, instance->id, instance->dao_sequence, dodag->id, opts, ptr - opts, dst); 00819 ns_dyn_mem_free(opts); 00820 00821 instance->dao_sequence_in_transit = instance->dao_sequence; 00822 instance->dao_sequence = rpl_seq_inc(instance->dao_sequence); 00823 instance->requested_dao_ack = need_ack; 00824 instance->dao_in_transit = true; 00825 if (instance->dao_attempt < 16) { 00826 uint32_t t = (uint32_t) rpl_policy_initial_dao_ack_wait(instance->domain, mop) << instance->dao_attempt; 00827 t = randLIB_randomise_base(t, 0x4000, 0xC000); 00828 instance->dao_retry_timer = t <= 0xffff ? t : 0xffff; 00829 } else { 00830 instance->dao_retry_timer = 0xffff; 00831 } 00832 tr_info("DAO tx %u seq attempts %u retry-timer %u", instance->dao_sequence_in_transit,instance->dao_attempt, instance->dao_retry_timer); 00833 } 00834 00835 #if 0 00836 /* This only sends a specific No-Path for one target, to one neighbour, in storing mode */ 00837 void rpl_instance_send_dao_no_path(rpl_instance_t *instance, rpl_dao_target_t *target, rpl_neighbour_t *neighbour) 00838 { 00839 //rpl_control_transmit(domain, NULL, ICMPV6_CODE_RPL_DAO, buf, dst); 00840 uint8_t dodagid = rpl_instance_id_is_local(instance->id) ? RPL_DAO_FLAG_DODAGID : 0; 00841 uint8_t base_size = dodagid ? 4 + 16 : 4; 00842 uint16_t opts_size = 20 + 6 + 6; /* Worst case - Target/Desc/Transit */ 00843 buffer_t *buf = buffer_get(base_size + opts_size); 00844 if (!buf) { 00845 /* Retrigger? */ 00846 return; 00847 } 00848 uint8_t *ptr = buffer_data_pointer(buf); 00849 00850 ptr[0] = instance->id; 00851 ptr[1] = dodagid; 00852 ptr[2] = 0; 00853 ptr[3] = instance->dao_sequence = rpl_seq_inc(instance->dao_sequence); 00854 if (dodagid) { 00855 memcpy(ptr + 4, dodag->id, 16); 00856 ptr += 16; 00857 } 00858 ptr = rpl_downward_write_target(ptr, target); 00859 ptr = rpl_downward_write_transit(ptr, target, path_control?, NULL, false); 00860 memcpy(buf + base_size, ptr, opts_size); 00861 const uint8_t *dst; 00862 if (storing) { 00863 dst = get_parent_ll_address(parent_idx); 00864 } else { 00865 dst = dodag->id; 00866 } 00867 rpl_control_transmit(domain, NULL, ICMPV6_CODE_RPL_DAO, buf, neighbour->ll_address); 00868 } 00869 #endif 00870 00871 #ifdef HAVE_RPL_ROOT 00872 static uint_fast8_t rpl_downward_path_control_to_preference(uint8_t pc) 00873 { 00874 if (pc >= 0x40) { 00875 return 1; 00876 } else if (pc >= 0x10) { 00877 return 2; 00878 } else if (pc >= 0x04) { 00879 return 3; 00880 } else { 00881 return 4; 00882 } 00883 } 00884 00885 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) 00886 { 00887 //rpl_dao_root_transit_t *old_first = ns_list_get_first(&target->info.root.transits); 00888 rpl_dao_root_transit_t *transit = NULL; 00889 ns_list_foreach(rpl_dao_root_transit_t, t, &target->info.root.transits) { 00890 if (addr_ipv6_equal(t->transit, parent)) { 00891 ns_list_remove(&target->info.root.transits, t); 00892 transit = t; 00893 /* Updating existing transit - invalidates costs only */ 00894 rpl_downward_paths_invalidate(target->instance); 00895 break; 00896 } 00897 } 00898 00899 if (!transit) { 00900 transit = rpl_alloc(sizeof(rpl_dao_root_transit_t)); 00901 if (!transit) { 00902 tr_warn("RPL DAO overflow (target=%s,transit=%s)", trace_ipv6_prefix(target->prefix, target->prefix_len), trace_ipv6(parent)); 00903 goto out; 00904 } 00905 transit->path_control = 0; 00906 /* A new transit invalidates the topo sort */ 00907 rpl_downward_topo_sort_invalidate(target->instance); 00908 } 00909 00910 transit->target = target; 00911 transit->path_control |= path_control; 00912 /* Initial transit cost is 1-4, depending on preference in Path Control. 00913 * Source routing errors from intermediate nodes may increase this. For 00914 * directly connected nodes, rpl_downward_compute_paths asks policy 00915 * to modify according to ETX (or whatever). 00916 */ 00917 transit->cost = rpl_downward_path_control_to_preference(transit->path_control); 00918 00919 memcpy(transit->transit, parent, 16); 00920 ns_list_add_to_end(&target->info.root.transits, transit); 00921 00922 out: 00923 return ns_list_get_first(&target->info.root.transits); 00924 } 00925 00926 static rpl_dao_target_t *rpl_downward_delete_root_transit(rpl_dao_target_t *target, rpl_dao_root_transit_t *transit) 00927 { 00928 ns_list_remove(&target->info.root.transits, transit); 00929 rpl_free(transit, sizeof *transit); 00930 if (ns_list_is_empty(&target->info.root.transits)) { 00931 rpl_delete_dao_target(target->instance, target); 00932 return NULL; 00933 } 00934 00935 rpl_downward_topo_sort_invalidate(target->instance); 00936 return target; 00937 } 00938 00939 void rpl_downward_transit_error(rpl_instance_t *instance, const uint8_t *target_addr, const uint8_t *transit_addr) 00940 { 00941 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 00942 if (!target->root) { 00943 continue; 00944 } 00945 if (!bitsequal(target_addr, target->prefix, target->prefix_len)) { 00946 continue; 00947 } 00948 ns_list_foreach_safe(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 00949 if (addr_ipv6_equal(transit_addr, transit->transit)) { 00950 /* 4 bit Path Control gives us an initial 1-4 cost. We then add something for every error. */ 00951 /* This should make lowest path cost algorithm cycle through alternatives */ 00952 /* When the DAO is refreshed, the cost is reset, so we forget accumulated errors. */ 00953 if (transit->cost < 0xFFFC) { 00954 transit->cost += 4; 00955 } else { 00956 transit->cost = 0xFFFF; 00957 } 00958 rpl_downward_paths_invalidate(instance); 00959 instance->srh_error_count++; 00960 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))) { 00961 rpl_instance_increment_dtsn(instance); 00962 } 00963 break; 00964 } 00965 } 00966 } 00967 } 00968 #endif // HAVE_RPL_ROOT 00969 00970 #ifdef HAVE_RPL_DAO_HANDLING 00971 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) 00972 { 00973 (void) status; 00974 const uint8_t *parent; 00975 /* Check transit length */ 00976 if (storing) { 00977 if (transit_opt[1] != 4) { 00978 return false; 00979 } 00980 parent = NULL; 00981 } else { 00982 if (transit_opt[1] != 20) { 00983 return false; 00984 } 00985 parent = transit_opt + 6; 00986 } 00987 bool external = transit_opt[2] & TRANSIT_FLAG_EXTERNAL; 00988 uint8_t path_control = transit_opt[3]; 00989 uint8_t path_sequence = transit_opt[4]; 00990 uint8_t path_lifetime = transit_opt[5]; 00991 00992 uint32_t lifetime; 00993 if (path_lifetime == 0xFF) { 00994 lifetime = 0xFFFFFFFF; 00995 } else { 00996 lifetime = (uint32_t) path_lifetime * dodag->config.lifetime_unit; 00997 } 00998 00999 rpl_dao_target_t *last_target = NULL; 01000 while (target_start < target_end) { 01001 switch (target_start[0]) { 01002 case RPL_TARGET_OPTION: 01003 { 01004 last_target = NULL; 01005 uint8_t prefix_len = target_start[3]; 01006 if (prefix_len > 128 || prefix_len > (target_start[1] - 2) * 8) { 01007 return false; 01008 } 01009 const uint8_t *prefix = target_start + 4; 01010 rpl_dao_target_t *target = rpl_instance_lookup_dao_target(dodag->instance, prefix, prefix_len); 01011 if (target) { 01012 /* Ignore DAOs for targets we're publishing ourselves */ 01013 if (target->published) { 01014 break; 01015 } 01016 /* No-Paths are special: version number isn't significant */ 01017 if (path_lifetime == 0) { 01018 tr_info("No-Path %s->%s", parent ? trace_ipv6(parent) : "", trace_ipv6_prefix(prefix, prefix_len)); 01019 if (storing) { 01020 ipv6_route_delete_with_info(prefix, prefix_len, interface_id, src, ROUTE_RPL_DAO, target, 0); 01021 /* If we have no DAO routes left for this target, kill it (we don't track who sends individual 01022 * DAOs in our target database - the only record we have is in the system routing table 01023 */ 01024 if (!ipv6_route_lookup_with_info(prefix, prefix_len, interface_id, NULL, ROUTE_RPL_DAO, target, 0)) { 01025 rpl_delete_dao_target(dodag->instance, target); 01026 *new_info = true; 01027 } 01028 } else { 01029 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01030 if (addr_ipv6_equal(transit->transit, parent)) { 01031 target = rpl_downward_delete_root_transit(target, transit); 01032 *new_info = true; 01033 break; 01034 } 01035 } 01036 } 01037 /* No more processing on this target - go to next option */ 01038 break; 01039 } 01040 /* A real path. Compare path sequence. */ 01041 rpl_cmp_t seq_cmp = rpl_seq_compare(path_sequence, target->path_sequence); 01042 01043 bool accept; 01044 if (storing) { 01045 /* For storing, follow the letter of spec. Can't afford for old route propagation to happen. */ 01046 accept = seq_cmp & (RPL_CMP_GREATER|RPL_CMP_EQUAL); 01047 } else { 01048 /* Lollipop counters don't necessarily work brilliantly after reboot - the path 01049 * sequence causes more problems than it solves for non-storing modes, where it's 01050 * the actual target owner sending the info. We don't have to worry about the 01051 * network storing stale data. So we're more flexible. 01052 */ 01053 if (path_sequence >= 128) { 01054 /* Always accept anything with sequence in the lollipop counter restart region */ 01055 accept = true; 01056 /* Also, we always refresh lifetime, even if sequence number is the same as stored */ 01057 target->lifetime = lifetime; 01058 } else if (external) { 01059 /* ZigBee IP requires external targets to use latest info and ignore sequence - 01060 * publishers can't really keep them in sync. We go along with this. 01061 */ 01062 accept = true; 01063 target->lifetime = lifetime; 01064 } else { 01065 accept = seq_cmp & (RPL_CMP_GREATER|RPL_CMP_EQUAL); 01066 } 01067 } 01068 if (!accept) { 01069 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); 01070 break; 01071 } 01072 /* If path sequence is different, we clear existing transits for this target */ 01073 if (!(seq_cmp & RPL_CMP_EQUAL)) { 01074 if (target->root) { 01075 ns_list_foreach_safe(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01076 ns_list_remove(&target->info.root.transits, transit); 01077 rpl_free(transit, sizeof *transit); 01078 } 01079 } 01080 if (storing) { 01081 ipv6_route_table_remove_info(-1, ROUTE_RPL_DAO, target); 01082 } 01083 target->path_control = 0; 01084 target->path_sequence = path_sequence; 01085 target->lifetime = lifetime; 01086 *new_info = true; 01087 } 01088 /* Then we proceed to add this transit to the target below */ 01089 } else if (path_lifetime != 0) { 01090 target = rpl_create_dao_target(dodag->instance, prefix, prefix_len, !storing); 01091 if (target) { 01092 target->path_sequence = path_sequence; 01093 target->lifetime = lifetime; 01094 } 01095 } 01096 01097 /* No-Paths don't reach here - we break out above */ 01098 if (target) { 01099 if (path_control &~ target->path_control) { 01100 target->path_control |= path_control; 01101 *new_info = true; 01102 } 01103 target->external = external; 01104 target->interface_id = interface_id; 01105 if (storing) { 01106 target->info.non_root.path_lifetime = path_lifetime; 01107 } 01108 01109 if (storing) { 01110 /* In Storing mode, add a route immediately */ 01111 ipv6_route_add_with_info(prefix, prefix_len, interface_id, src, ROUTE_RPL_DAO, target, 0, target->lifetime, 0); 01112 } else { 01113 rpl_dao_root_transit_t *transit = rpl_downward_add_root_transit(target, parent, path_control); 01114 #if 0 01115 /* In Non-Storing mode, add the transit to the target, and we'll re-evaluate system routes later */ 01116 ipv6_route_table_remove_info(-1, ROUTE_RPL_DAO_SR, target); 01117 if (transit_opt) { 01118 if (protocol_interface_address_compare(parent) == 0) { 01119 /* If we're transit, it's on-link */ 01120 ipv6_route_add_with_info(prefix, prefix_len, interface_id, NULL, ROUTE_RPL_DAO_SR, target, 0, target->lifetime, 0); 01121 } else { 01122 ipv6_route_add_with_info(prefix, prefix_len, interface_id, parent, ROUTE_RPL_DAO_SR, target, 0, target->lifetime, 0); 01123 } 01124 } 01125 #else 01126 if (transit) { 01127 ipv6_route_add_with_info(prefix, prefix_len, interface_id, ADDR_UNSPECIFIED, ROUTE_RPL_DAO_SR, target, 0, target->lifetime, 0); 01128 } 01129 #endif 01130 } 01131 } 01132 01133 last_target = target; 01134 break; 01135 } 01136 case RPL_TARGET_DESC_OPTION: 01137 if (target_start[1] == 4 && last_target) { 01138 last_target->descriptor_present = true; 01139 last_target->descriptor = common_read_32_bit(target_start + 2); 01140 } 01141 break; 01142 case RPL_PAD1_OPTION: 01143 target_start++; 01144 continue; 01145 } 01146 target_start += 2 + target_start[1]; 01147 } 01148 01149 return true; 01150 } 01151 #endif // HAVE_RPL_DAO_HANDLING 01152 01153 #ifdef HAVE_RPL_ROOT 01154 /* Link the graph ready for routing. "Canonical" database information stores 01155 * transits per target - in effect edges from children to parents. 01156 * For our path finding we need to match transits by prefix - eg all 2002::xx 01157 * transits might go via one 2002::/64 target - and we want to turn it around 01158 * so that our edges point from parents to children. 01159 * 01160 * This fills in (from scratch): 01161 * 01162 * transit::parent :-> matched target, or NULL for disconnected/DODAG root (us) 01163 * 01164 * target::connected := true for targets directly connected to DODAG root 01165 * 01166 * target::info.root.children 01167 * and instance::root_children := list of transits with this target/root as parent 01168 * 01169 * target::info.root.cost := number of transits connected to parent targets (connections to root not included) 01170 */ 01171 static void rpl_downward_link_transits_to_targets(rpl_instance_t *instance) 01172 { 01173 ns_list_init(&instance->root_children); 01174 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01175 target->info.root.cost = 0; 01176 target->connected = false; 01177 ns_list_init(&target->info.root.children); 01178 } 01179 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01180 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01181 if (protocol_interface_address_compare(transit->transit) == 0) { 01182 /* It points to us (the DODAG root) - mark this with NULL */ 01183 transit->parent = NULL; 01184 target->connected = true; 01185 /* Links to the root don't count as incoming transits */ 01186 ns_list_add_to_end(&instance->root_children, transit); 01187 } else { 01188 transit->parent = rpl_instance_match_dao_target(instance, transit->transit, 128); 01189 if (transit->parent) { 01190 target->info.root.cost++; 01191 ns_list_add_to_end(&transit->parent->info.root.children, transit); 01192 } 01193 } 01194 } 01195 } 01196 } 01197 01198 /* Subroutine for topo sort - an edge has been removed, either because the 01199 * parent is moved to the sorted list, or we're breaking a loop. Update 01200 * the "incoming edges" count in the child, and maybe move it to the top nodes list. 01201 */ 01202 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) 01203 { 01204 rpl_dao_target_t *child = transit->target; 01205 01206 if (child->info.root.cost > 0) { 01207 child->info.root.cost--; 01208 } else { 01209 tr_err("topo sort count error"); 01210 } 01211 /* If this child has no more incoming, move it onto the "top nodes" list */ 01212 if (child->info.root.cost == 0) { 01213 ns_list_remove(graph, child); 01214 ns_list_add_to_end(top_nodes, child); 01215 } 01216 } 01217 01218 static void rpl_downward_topo_sort_break_loop(rpl_dao_target_list_t *graph, rpl_dao_target_list_t *top_nodes) 01219 { 01220 rpl_dao_root_transit_t *kill_transit = NULL; 01221 01222 /* Don't expect this to happen much, so not particularly optimised - we kill 1 transit to break the loop */ 01223 /* First choose a target with the most transits - we want to delete spare ones. */ 01224 ns_list_foreach(rpl_dao_target_t, target, graph) { 01225 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.children) { 01226 if (!kill_transit) { 01227 goto kill_candidate; 01228 } 01229 /* Prefer to delete transits to already-connected targets. In a 01230 * simple scenario with one loop, for example: 01231 * 01232 * Root--->A--->B--->C--->D 01233 * ^------ / 01234 * 01235 * the initial pass will prune to: 01236 * 01237 * B--->C--->D 01238 * ^-------/ 01239 * 01240 * and only B will be marked "connected". D->B is the link to 01241 * kill to get everyone else connected. (Deleting B->C would 01242 * leave C unconnected. Deleting C->D would leave D unconnected.) 01243 * 01244 * With alternate paths like: 01245 * 01246 * /--------v 01247 * Root--->A--->B--->C--->D 01248 * ^------ / 01249 * 01250 * it would prune to 01251 * 01252 * B--->C--->D 01253 * ^------ / 01254 * 01255 * but this time both B and C would be connected. Deleting 01256 * either D->B or B->C would result in valid acyclic graphs, although 01257 * an optimal link might be lost. 01258 * 01259 * /--------v 01260 * Root--->A--->B--->C--->D 01261 * 01262 * /--------v 01263 * Root--->A--->B C--->D 01264 * ^-------/ 01265 */ 01266 if (!kill_transit->target->connected && transit->target->connected) { 01267 goto kill_candidate; 01268 } else if (kill_transit->target->connected && !transit->target->connected) { 01269 continue; 01270 } 01271 01272 /* Prefer to kill a higher-cost link */ 01273 if (kill_transit->cost < transit->cost) { 01274 goto kill_candidate; 01275 } else if (kill_transit->cost > transit->cost) { 01276 continue; 01277 } 01278 kill_candidate: 01279 kill_transit = transit; 01280 } 01281 } 01282 01283 /* Hopefully we killed found transit to a connected node to kill. */ 01284 /* If we didn't, it means we're on an isolated island, so we're dooomed anyway... */ 01285 01286 /* This removes it from our routing graph, but not from the master database */ 01287 ns_list_remove(&kill_transit->parent->info.root.children, kill_transit); 01288 rpl_downward_topo_sort_edge_removed(kill_transit, graph, top_nodes); 01289 } 01290 01291 /* Topologically sort instance->dao_targets - closest to border router placed at start */ 01292 static void rpl_downward_topo_sort(rpl_instance_t *instance) 01293 { 01294 if (instance->root_topo_sort_valid) { 01295 return; 01296 } 01297 01298 rpl_downward_link_transits_to_targets(instance); 01299 01300 rpl_dao_target_list_t sorted = NS_LIST_INIT(sorted); 01301 rpl_dao_target_list_t top_nodes = NS_LIST_INIT(top_nodes); 01302 01303 /* Find all the topmost targets - most should have been marked "connected", ie they 01304 * have exactly 1 link to the DODAG root. Some may be disconnected. */ 01305 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01306 if (target->info.root.cost == 0) { 01307 ns_list_remove(&instance->dao_targets, target); 01308 ns_list_add_to_end(&top_nodes, target); 01309 } 01310 } 01311 01312 retry_after_loop_break:; 01313 /* Run the sort - targets are pulled off 'instance->dao_targets', and placed onto 'sorted' */ 01314 01315 rpl_dao_target_t *target; 01316 while ((target = ns_list_get_first(&top_nodes)) != NULL) { 01317 /* Take any topmost node, place on the end of the sorted list */ 01318 ns_list_remove(&top_nodes, target); 01319 ns_list_add_to_end(&sorted, target); 01320 01321 /* Decrement incoming link count on all children */ 01322 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.children) { 01323 rpl_downward_topo_sort_edge_removed(transit, &instance->dao_targets, &top_nodes); 01324 /* If this node is connected, the child is connected */ 01325 if (target->connected) { 01326 transit->target->connected = true; 01327 } 01328 01329 } 01330 } 01331 01332 if (!ns_list_is_empty(&instance->dao_targets)) { 01333 /* Didn't manage to empty the graph, so we have a loop - not a DAG */ 01334 do { 01335 rpl_downward_topo_sort_break_loop(&instance->dao_targets, &top_nodes); 01336 } while (ns_list_is_empty(&top_nodes)); 01337 goto retry_after_loop_break; 01338 } 01339 01340 /* Transfer sorted list back onto instance (dao_targets must be empty at this point) */ 01341 ns_list_concatenate(&instance->dao_targets, &sorted); 01342 instance->root_topo_sort_valid = true; 01343 } 01344 01345 /* Call when topo sort may have changed (or child links broken) - this invalidates everything */ 01346 static void rpl_downward_topo_sort_invalidate(rpl_instance_t *instance) 01347 { 01348 instance->root_topo_sort_valid = false; 01349 rpl_downward_paths_invalidate(instance); 01350 } 01351 01352 static void rpl_downward_update_path_cost_to_children(rpl_dao_root_transit_children_list_t *children, uint16_t parent_cost) 01353 { 01354 ns_list_foreach(rpl_dao_root_transit_t, transit, children) { 01355 rpl_dao_target_t *child = transit->target; 01356 uint16_t transit_cost = transit->cost; 01357 /* For directly-connected paths, modify for ETX or similar */ 01358 if (parent_cost == 0 && child->prefix_len == 128) { 01359 transit_cost = rpl_policy_modify_downward_cost_to_root_neighbour(child->instance->domain, child->interface_id, child->prefix, transit->cost); 01360 } 01361 if (child->info.root.cost > parent_cost + transit_cost) { 01362 /* Note new best cost to child, and make this transit the child's first/best */ 01363 child->info.root.cost = parent_cost + transit_cost; 01364 if (transit != ns_list_get_first(&child->info.root.transits)) { 01365 ns_list_remove(&child->info.root.transits, transit); 01366 ns_list_add_to_start(&child->info.root.transits, transit); 01367 } 01368 } 01369 } 01370 } 01371 01372 void rpl_downward_compute_paths(rpl_instance_t *instance) 01373 { 01374 if (instance->root_paths_valid) { 01375 return; 01376 } 01377 01378 /* First get targets into a topological sort - also breaks loops */ 01379 rpl_downward_topo_sort(instance); 01380 01381 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01382 target->info.root.cost = 0xFFFFFFFF; 01383 } 01384 01385 /* First process the direct root->child links, giving inital link costs */ 01386 rpl_downward_update_path_cost_to_children(&instance->root_children, 0); 01387 01388 /* Now process every node in turn */ 01389 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01390 /* Update connected flag - could be invalid due to node removal that didn't redo topo sort */ 01391 target->connected = target->info.root.cost != 0xFFFFFFFF; 01392 if (target->connected) { 01393 rpl_downward_update_path_cost_to_children(&target->info.root.children, target->info.root.cost); 01394 } 01395 } 01396 01397 instance->root_paths_valid = true; 01398 } 01399 01400 /* Called when path costs may have changed (but not topo sort) */ 01401 void rpl_downward_paths_invalidate(rpl_instance_t *instance) 01402 { 01403 instance->root_paths_valid = false; 01404 rpl_data_sr_invalidate(); 01405 } 01406 #endif // HAVE_RPL_ROOT 01407 01408 #ifdef HAVE_RPL_DAO_HANDLING 01409 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) 01410 { 01411 rpl_dodag_t *dodag = rpl_instance_current_dodag(instance); 01412 if (!dodag) { 01413 return false; 01414 } 01415 if (multicast) { 01416 /* We don't handle multicast DAOs at all yet */ 01417 return false; 01418 } 01419 bool storing; 01420 switch (rpl_dodag_mop(dodag)) { 01421 default: 01422 case RPL_MODE_NO_DOWNWARD: 01423 return false; 01424 case RPL_MODE_NON_STORING: 01425 if (!rpl_dodag_am_root(dodag) || addr_is_ipv6_link_local(src)) { 01426 return false; 01427 } 01428 storing = false; 01429 break; 01430 case RPL_MODE_STORING: 01431 case RPL_MODE_STORING_MULTICAST: 01432 if (instance->current_rank == RPL_RANK_INFINITE || !addr_is_ipv6_link_local(src)) { 01433 return false; 01434 } 01435 storing = true; 01436 break; 01437 } 01438 01439 const uint8_t *start = opts, *end = opts + opts_len; 01440 01441 /* Basic format is ("group of targets", "group of transits"), repeated. 01442 * All the transits apply to all the preceding targets. So parsing is: 01443 * 1) When we see next target, and target group is closed, remember start of target group, open end. 01444 * 2) When we see a transit, mark end of target group if not already closed. 01445 * 3) Then for any transit, process the entire target group. 01446 */ 01447 const uint8_t *target_start = NULL, *target_end = opts; 01448 01449 bool new_info = false; 01450 *status = 0; 01451 01452 while (start < end) { 01453 switch (start[0]) { 01454 case RPL_TARGET_OPTION: 01455 if (target_end) { 01456 target_start = start; 01457 target_end = NULL; 01458 } 01459 break; 01460 case RPL_TRANSIT_OPTION: 01461 if (target_start) { 01462 if (!target_end) { 01463 target_end = start; 01464 } 01465 rpl_downward_process_targets_for_transit(dodag, storing, src, interface_id, target_start, target_end, start, &new_info, status); 01466 } else { 01467 tr_warn("Transit without Targets"); 01468 } 01469 break; 01470 case RPL_PAD1_OPTION: 01471 start++; 01472 continue; 01473 } 01474 start += 2 + start[1]; 01475 } 01476 01477 if (new_info && storing) { 01478 rpl_instance_dao_trigger(instance, 0); 01479 } 01480 01481 return true; 01482 } 01483 #endif // HAVE_RPL_DAO_HANDLING 01484 01485 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) 01486 { 01487 if (!instance->dao_in_transit || dao_sequence != instance->dao_sequence_in_transit) { 01488 return; 01489 } 01490 01491 if (src) { 01492 ipv6_neighbour_reachability_confirmation(src, interface_id); 01493 } 01494 01495 bool retry = false; 01496 if (status == 0) { 01497 tr_debug("DAO-ACK RX"); /* Some tests rely on this debug */ 01498 } else { 01499 if (src) { 01500 tr_warn("DAO rejection from %s: status=%d", trace_ipv6(src), status); 01501 } else { 01502 tr_warn("DAO timeout"); 01503 retry = true; 01504 } 01505 } 01506 01507 rpl_dodag_t *dodag = rpl_instance_current_dodag(instance); 01508 const rpl_dodag_conf_t *conf = dodag? rpl_dodag_get_config(dodag) : NULL; 01509 instance->dao_in_transit = false; 01510 instance->dao_retry_timer = 0; 01511 if (!retry) { 01512 instance->dao_attempt = 0; 01513 } 01514 01515 bool more_to_do = false; 01516 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01517 if (target->root) { 01518 continue; 01519 } 01520 tr_debug("tgt %s - pc %02x, assigned %02x, assigning %02x, life %02x, rfr %"PRIu32, 01521 trace_ipv6_prefix(target->prefix, target->prefix_len), 01522 target->path_control, 01523 target->info.non_root.pc_assigned, 01524 target->info.non_root.pc_assigning, 01525 target->info.non_root.path_lifetime, 01526 target->info.non_root.refresh_timer); 01527 target->info.non_root.pc_assigning &= target->path_control; 01528 if (target->info.non_root.pc_assigning) { 01529 if (!retry) { 01530 target->info.non_root.pc_assigned |= target->info.non_root.pc_assigning; 01531 } else { 01532 target->info.non_root.pc_to_retry |= target->info.non_root.pc_assigning; 01533 } 01534 target->info.non_root.pc_assigning = 0; 01535 } 01536 target->info.non_root.pc_assigned &= target->path_control; 01537 if (target->info.non_root.pc_assigned != target->path_control) { 01538 more_to_do = true; 01539 } else { 01540 if (target->published && target->info.non_root.refresh_timer == 0) { 01541 uint32_t t; 01542 if (conf && target->info.non_root.path_lifetime != 0xFF) { 01543 t = (uint32_t) target->info.non_root.path_lifetime * conf->lifetime_unit; 01544 /* Refresh between 1/2 and 3/4 of lifetime */ 01545 t = randLIB_randomise_base(t, 0x4000, 0x6000); 01546 } else { 01547 t = 0xFFFFFFFF; 01548 } 01549 #ifdef MINIMUM_DAO_TARGET_REFRESH 01550 if (t > MINIMUM_DAO_TARGET_REFRESH) { 01551 t = randLIB_randomise_base(MINIMUM_DAO_TARGET_REFRESH, 0x7333, 0x8CCD); /* +/- 10% */ 01552 } 01553 #endif 01554 target->info.non_root.refresh_timer = t; 01555 tr_debug("set rfr to %"PRIu32, t); 01556 } 01557 } 01558 } 01559 01560 if (more_to_do) { 01561 rpl_instance_dao_trigger(instance, 1); 01562 } else { 01563 rpl_control_event(instance->domain, RPL_EVENT_DAO_DONE); 01564 } 01565 } 01566 01567 void rpl_instance_dao_request(struct rpl_instance *instance, struct rpl_neighbour *neighbour) 01568 { 01569 uint8_t pc_mask = neighbour ? neighbour->dao_path_control : 0xFF; 01570 01571 if (!pc_mask) { 01572 return; 01573 } 01574 01575 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01576 if (!target->root) { 01577 target->info.non_root.pc_assigned &= ~pc_mask; 01578 target->info.non_root.pc_to_retry &= ~pc_mask; 01579 } 01580 } 01581 01582 rpl_instance_dao_trigger(instance, 0); 01583 } 01584 01585 01586 void rpl_downward_dao_slow_timer(rpl_instance_t *instance, uint16_t seconds) 01587 { 01588 if (!instance) { 01589 return; 01590 } 01591 /* Process lifetimes on all targets for expiry */ 01592 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01593 if (target->lifetime == 0xFFFFFFFF) { 01594 continue; 01595 } 01596 if (target->lifetime > seconds) { 01597 target->lifetime -= seconds; 01598 continue; 01599 } 01600 rpl_delete_dao_target(instance, target); 01601 } 01602 01603 /* Perform target auto-refresh for published targets */ 01604 ns_list_foreach_safe(rpl_dao_target_t, target, &instance->dao_targets) { 01605 if (!target->published) { 01606 continue; 01607 } 01608 if (target->info.non_root.refresh_timer == 0xFFFFFFFF || target->info.non_root.refresh_timer == 0) { 01609 continue; 01610 } 01611 if (target->info.non_root.refresh_timer > seconds) { 01612 target->info.non_root.refresh_timer -= seconds; 01613 continue; 01614 } 01615 /* Refresh the DAO target */ 01616 target->info.non_root.refresh_timer = 0; 01617 rpl_downward_target_refresh(target); 01618 rpl_instance_dao_trigger(instance, 0); 01619 } 01620 } 01621 01622 void rpl_downward_dao_timer(rpl_instance_t *instance, uint16_t ticks) 01623 { 01624 if (instance->dao_retry_timer) { 01625 if (instance->dao_retry_timer > ticks) { 01626 instance->dao_retry_timer -= ticks; 01627 } else { 01628 instance->dao_retry_timer = 0; 01629 if (!instance->requested_dao_ack) { 01630 /* Act as if ACK arrived at first retry point (gives them 01631 * time to send a failure). 01632 */ 01633 rpl_instance_dao_acked(instance, NULL, -1, instance->dao_sequence_in_transit, 0); 01634 } else { 01635 rpl_instance_dao_acked(instance, NULL, -1, instance->dao_sequence_in_transit, 0xFF); 01636 } 01637 } 01638 } 01639 01640 if (instance->delay_dao_timer) { 01641 if (instance->delay_dao_timer > ticks) { 01642 instance->delay_dao_timer -= ticks; 01643 } else { 01644 instance->delay_dao_timer = 0; 01645 rpl_instance_send_dao_update(instance); 01646 } 01647 } 01648 } 01649 01650 void rpl_downward_print_instance(rpl_instance_t *instance, route_print_fn_t *print_fn) 01651 { 01652 if (ns_list_is_empty(&instance->dao_targets)) { 01653 return; 01654 } 01655 print_fn("DAO Targets:"); 01656 if (rpl_instance_am_root(instance)) { 01657 rpl_downward_compute_paths(instance); 01658 } 01659 ns_list_foreach(rpl_dao_target_t, target, &instance->dao_targets) { 01660 01661 char str_buf[44]; 01662 ip6_prefix_tos(target->prefix, target->prefix_len, str_buf); 01663 #ifdef HAVE_RPL_ROOT 01664 if (target->root) { 01665 print_fn(" %-40s %02x seq=%d%s cost=%"PRIu32"%s%s%s", 01666 str_buf, 01667 target->path_control, target->path_sequence, target->need_seq_inc ? "+" : "", 01668 target->info.root.cost, 01669 target->published ? " (pub)" : "", 01670 target->external ? " (E)" : "", 01671 target->connected ? "" : " (disconnected)"); 01672 ns_list_foreach(rpl_dao_root_transit_t, transit, &target->info.root.transits) { 01673 // Reuse str_buf as it's no longer needed and it's large enough for ROUTE_PRINT_ADDR_STR_FORMAT. 01674 print_fn(" ->%-36s %02x cost=%"PRIu16, ROUTE_PRINT_ADDR_STR_FORMAT(str_buf, transit->transit), transit->path_control, transit->cost); 01675 } 01676 } else 01677 #endif 01678 { 01679 print_fn(" %-40s %02x seq=%d%s%s%s", 01680 str_buf, 01681 target->path_control, target->path_sequence, target->need_seq_inc ? "+" : "", 01682 target->published ? " (pub)" : "", 01683 target->external ? " (E)" : ""); 01684 } 01685 } 01686 } 01687 01688 #endif /* HAVE_RPL */
Generated on Tue Aug 9 2022 00:37:18 by
1.7.2