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