thread_routing.c

00001 /*
00002  * Copyright (c) 2014-2018, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: BSD-3-Clause
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions are met:
00007  *
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. Neither the name of the copyright holder nor the
00014  *    names of its contributors may be used to endorse or promote products
00015  *    derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00018  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
00021  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00022  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00023  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00024  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00025  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00026  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00027  * POSSIBILITY OF SUCH DAMAGE.
00028  */
00029 /*
00030  * Thread-specific routing functionality
00031  *
00032  * draft-kelsey-thread-routing-00
00033  */
00034 
00035 #include "nsconfig.h"
00036 #include <string.h>
00037 #include <ns_types.h>
00038 #include <ns_list.h>
00039 #include <randLIB.h>
00040 #include <nsdynmemLIB.h>
00041 
00042 #define THREAD_ROUTING_FN extern
00043 
00044 #include  <net_thread_test.h>
00045 #include "ns_trace.h"
00046 #include "common_functions.h"
00047 #include "NWK_INTERFACE/Include/protocol.h"
00048 #include "MLE/mle.h"
00049 #include "6LoWPAN/Mesh/mesh.h"
00050 #include "6LoWPAN/Thread/thread_common.h"
00051 #include "6LoWPAN/Thread/thread_nd.h"
00052 #include "6LoWPAN/Thread/thread_routing.h"
00053 #include "6LoWPAN/Thread/thread_leader_service.h"
00054 #include "6LoWPAN/MAC/mac_helper.h"
00055 #include "Service_Libs/mac_neighbor_table/mac_neighbor_table.h"
00056 
00057 #define TRACE_GROUP "trou"
00058 
00059 /* MLE Route Data bit assignments (draft-kelsey-thread-routing-00) */
00060 #define ROUTE_DATA_OUT_MASK     0xC0
00061 #define ROUTE_DATA_OUT_SHIFT    6
00062 #define ROUTE_DATA_IN_MASK      0x30
00063 #define ROUTE_DATA_IN_SHIFT     4
00064 #define ROUTE_DATA_COST_MASK    0x0F
00065 #define ROUTE_DATA_OURSELF      0x01
00066 
00067 /*
00068  * MAX_LINK_AGE must be > 1.5 * trickle Imax, as that's the maximum spacing
00069  * between advert transmissions (assuming all peers have same Imax, as they
00070  * should)
00071  *
00072  * |---Imax---|---Imax---|  (Two Imax intervals, transmitting at Imax/2 in first
00073  *       t               t   and Imax-1 in second, so 1.5*Imax - 1 apart).
00074  */
00075 #define MAX_LINK_AGE 100*10     /* 100 seconds */
00076 
00077 #define LINK_AGE_STATIC 0xFFF  /* Magic number to indicate "never expire" */
00078 
00079 #ifdef HAVE_THREAD_ROUTER
00080 
00081 static trickle_params_t thread_mle_advert_trickle_params = {
00082     .Imin = 1 * 10,     /* 1 second; ticks are 100ms */
00083     .Imax = 32 * 10,    /* 32 seconds */
00084     .k = 0,             /* infinity - no consistency checking */
00085     .TimerExpirations = TRICKLE_EXPIRATIONS_INFINITE
00086 };
00087 
00088 static bool thread_update_fast_route(thread_info_t *thread, thread_router_id_t dest);
00089 static void thread_update_fast_route_table(thread_info_t *thread);
00090 
00091 bool router_id_sequence_is_greater(const thread_routing_info_t *routing, uint8_t seq)
00092 {
00093     return !routing->router_id_sequence_valid || common_serial_number_greater_8(seq, routing->router_id_sequence);
00094 }
00095 
00096 /*
00097  * Hysteresis for quality changes in dB. Note that in this implementation, given
00098  * the thresholds, this must be less than 2dB. At 1dB, quality will switch from
00099  * "2dB" to "BAD" only when link margin drops below 1dB.
00100  */
00101 #define LINK_QUALITY_HYSTERESIS (1 << THREAD_LINK_MARGIN_SCALING)   /* 1dB */
00102 
00103 static thread_link_margin_t link_quality_to_margin_lower_bound(thread_link_quality_e quality)
00104 {
00105     switch (quality) {
00106         case QUALITY_20dB:
00107             return 20 << THREAD_LINK_MARGIN_SCALING;
00108         case QUALITY_10dB:
00109             return 10 << THREAD_LINK_MARGIN_SCALING;
00110         case QUALITY_2dB:
00111             return 2 << THREAD_LINK_MARGIN_SCALING;
00112         default:
00113             return 0;
00114     }
00115 }
00116 
00117 static thread_link_margin_t link_quality_to_margin_upper_bound(thread_link_quality_e quality)
00118 {
00119     switch (quality) {
00120         case QUALITY_10dB:
00121             return 20 << THREAD_LINK_MARGIN_SCALING;
00122         case QUALITY_2dB:
00123             return 10 << THREAD_LINK_MARGIN_SCALING;
00124         case QUALITY_BAD:
00125             return 2 << THREAD_LINK_MARGIN_SCALING;
00126         default:
00127             return THREAD_LINK_MARGIN_MAX;
00128     }
00129 }
00130 static thread_link_quality_e link_margin_to_quality_with_hysteresis(thread_link_margin_t margin, thread_link_quality_e old_quality)
00131 {
00132     thread_link_quality_e new_quality = thread_link_margin_to_quality(margin);
00133 
00134     if ((new_quality > old_quality && margin > link_quality_to_margin_upper_bound(old_quality) + LINK_QUALITY_HYSTERESIS) ||
00135             (new_quality < old_quality && margin < link_quality_to_margin_lower_bound(old_quality) - LINK_QUALITY_HYSTERESIS)) {
00136         return new_quality;
00137     } else {
00138         return old_quality;
00139     }
00140 }
00141 
00142 static bool cost_less(thread_route_cost_t a, thread_route_cost_t b)
00143 {
00144     if (a == THREAD_COST_INFINITE) {
00145         return false;
00146     } else if (b == THREAD_COST_INFINITE) {
00147         return true;
00148     } else {
00149         return a < b;
00150     }
00151 }
00152 
00153 bool thread_i_am_router(const protocol_interface_info_entry_t *cur)
00154 {
00155     return cur->thread_info && cur->mac_parameters && thread_is_router_addr(mac_helper_mac16_address_get(cur));
00156 }
00157 
00158 
00159 /* Look up a router in our list of neighbour routers - return NULL if not a neighbour */
00160 static thread_router_link_t *thread_get_neighbour_router_by_id(thread_routing_info_t *routing, thread_router_id_t id)
00161 {
00162     ns_list_foreach(thread_router_link_t, neighbour, &routing->link_set) {
00163         if (neighbour->router_id == id) {
00164             return neighbour;
00165         }
00166     }
00167 
00168     return NULL;
00169 }
00170 
00171 static inline thread_link_quality_e thread_quality_combine(thread_link_quality_e in, thread_link_quality_e out)
00172 {
00173     thread_link_quality_e q;
00174 
00175     if (out < in) {
00176         q = out;
00177     } else {
00178         q = in;
00179     }
00180 
00181     return q;
00182 }
00183 
00184 /* Return the quality (worse of incoming and outgoing quality) for a neighbour router */
00185 static inline thread_link_quality_e thread_neighbour_router_quality(const thread_router_link_t *neighbour)
00186 {
00187     return thread_quality_combine((thread_link_quality_e) neighbour->incoming_quality, (thread_link_quality_e) neighbour->outgoing_quality);
00188 }
00189 
00190 
00191 /* Return the quality for a neighbour router; return QUALITY_BAD if not a neighbour */
00192 static thread_link_quality_e thread_get_neighbour_router_quality(thread_routing_info_t *routing, thread_router_id_t id)
00193 {
00194     thread_router_link_t *neighbour = thread_get_neighbour_router_by_id(routing, id);
00195     if (!neighbour) {
00196         return QUALITY_BAD;
00197     }
00198 
00199     return thread_neighbour_router_quality(neighbour);
00200 }
00201 
00202 /* Return the routing cost for a neighbour router */
00203 static thread_route_cost_t thread_neighbour_router_cost(const thread_router_link_t *neighbour)
00204 {
00205     return thread_link_quality_to_cost(thread_neighbour_router_quality(neighbour));
00206 }
00207 
00208 /* Return the routing cost for a neighbour router; return THREAD_COST_INFINITE if
00209  * not a neighbour.
00210  */
00211 static thread_route_cost_t thread_get_neighbour_router_cost(thread_routing_info_t *routing, thread_router_id_t id)
00212 {
00213     return thread_link_quality_to_cost(thread_get_neighbour_router_quality(routing, id));
00214 }
00215 
00216 static thread_route_t *thread_get_route_entry_by_id(thread_routing_info_t *routing, thread_router_id_t id)
00217 {
00218     ns_list_foreach(thread_route_t, r, &routing->route_set) {
00219         if (r->destination == id) {
00220             return r;
00221         }
00222     }
00223 
00224     return NULL;
00225 }
00226 
00227 static thread_route_t *thread_delete_route_entry_by_id(thread_info_t *thread, thread_router_id_t id)
00228 {
00229     thread_route_t *r = thread_get_route_entry_by_id(&thread->routing, id);
00230     if (r) {
00231         ns_list_remove(&thread->routing.route_set, r);
00232         ns_dyn_mem_free(r);
00233         if (thread_update_fast_route(thread, id)) {
00234             trickle_inconsistent_heard(&thread->routing.mle_advert_timer, &thread_mle_advert_trickle_params);
00235         }
00236     }
00237 
00238     return NULL;
00239 }
00240 
00241 /* Routing function for Mesh layer */
00242 static int_fast8_t thread_route_fn(
00243     protocol_interface_info_entry_t *cur,
00244     uint_fast8_t last_hop_addr_len, const uint8_t last_hop_addr[last_hop_addr_len],
00245     uint_fast8_t addr_len, const uint8_t dest_addr[addr_len],
00246     mesh_routing_route_response_t *resp)
00247 {
00248     if (addr_len != 2) {
00249         return -1;
00250     }
00251     uint16_t mac16  = mac_helper_mac16_address_get(cur);
00252     thread_info_t *thread = cur->thread_info;
00253     if (!thread  || mac16 >= 0xfffe) {
00254         return -1;
00255     }
00256 
00257 
00258     if (!thread_is_router_addr(mac16)) {
00259         /* We're just a leaf - always send to our parent router */
00260         resp->addr_len = 2;
00261         common_write_16_bit(thread_router_addr_from_addr(mac16), resp->address);
00262         return 0;
00263     }
00264 
00265     uint16_t dest = common_read_16_bit(dest_addr);
00266     uint16_t dest_router_addr = thread_router_addr_from_addr(dest);
00267     if (dest_router_addr == mac16) {
00268         /* We're this device's parent - transmit direct to it */
00269         mac_neighbor_table_entry_t *entry = mac_neighbor_table_address_discover(mac_neighbor_info(cur), dest_addr, ADDR_802_15_4_SHORT );
00270         if (!entry || !entry->ffd_device ) {
00271             /* To cover some of draft-kelsey-thread-network-data-00, we send the
00272              * packet up to our own IP layer in the case where it's addressed to
00273              * an unrecognised child. The special IP forwarding rules can then
00274              * generate an ICMP message. Also catching reduced function device here.
00275              */
00276             resp->intercept = true;
00277             return 0;
00278         }
00279         resp->addr_len = 2;
00280         common_write_16_bit(dest, resp->address);
00281         return 0;
00282     }
00283 
00284     thread_router_id_t dest_router_id = thread_router_id_from_addr(dest_router_addr);
00285     if (thread->routing.fast_route_table[dest_router_id] >= N_THREAD_ROUTERS) {
00286         return -1;
00287     }
00288 
00289     thread_router_id_t next_hop_router_id = thread->routing.fast_route_table[dest_router_id];
00290     uint16_t next_hop_router_addr = thread_router_addr_from_id(next_hop_router_id);
00291 
00292     /* 2-hop loop detection required by Thread spec */
00293     if (last_hop_addr_len == 2 && next_hop_router_addr == common_read_16_bit(last_hop_addr)) {
00294         tr_debug("%d: two-hop loop detected", dest_router_id);
00295         thread_delete_route_entry_by_id(thread, dest_router_id);
00296         // Don't drop packet - we still forward, which gives other hop
00297         // a chance to detect the loop. If it comes back again, then we
00298         // won't have a route that time. (Spec isn't explicit here -
00299         // found this works better than dropping).
00300     }
00301 
00302     resp->addr_len = 2;
00303     common_write_16_bit(next_hop_router_addr, resp->address);
00304     return 0;
00305 }
00306 
00307 /* First hop function for Mesh layer */
00308 static int_fast8_t thread_first_hop_fn(
00309     protocol_interface_info_entry_t *cur,
00310     uint_fast8_t addr_len, const uint8_t dest_addr[addr_len],
00311     mesh_routing_route_response_t *resp)
00312 {
00313     /* Re-use the routing function */
00314     return thread_route_fn(cur, 0, NULL, addr_len, dest_addr, resp);
00315 }
00316 
00317 static thread_route_cost_t thread_compute_route_cost(thread_routing_info_t *routing, thread_router_id_t dest, thread_router_id_t *next_hop)
00318 {
00319     /* Never attempt to route if router ID is known invalid */
00320     if (routing->fast_route_table[dest] == FAST_ROUTE_INVALID_ID) {
00321         return THREAD_COST_INFINITE;
00322     }
00323 
00324     /* Check cost for direct transmission */
00325     thread_route_cost_t cost_direct = thread_get_neighbour_router_cost(routing, dest);
00326 
00327     /* Then cost for multihop transmission */
00328     thread_route_cost_t cost_multihop = THREAD_COST_INFINITE;
00329     thread_route_t *route_entry = thread_get_route_entry_by_id(routing, dest);
00330     if (route_entry) {
00331         thread_route_cost_t next_hop_cost = thread_get_neighbour_router_cost(routing, route_entry->next_hop);
00332         cost_multihop = thread_link_cost_sum(route_entry->route_cost, next_hop_cost);
00333     }
00334 
00335     if (cost_direct == THREAD_COST_INFINITE && cost_multihop == THREAD_COST_INFINITE) {
00336         return THREAD_COST_INFINITE;
00337     } else {
00338         if (route_entry && cost_less(cost_multihop, cost_direct)) {
00339             if (next_hop) {
00340                 *next_hop = route_entry->next_hop;
00341             }
00342             return cost_multihop;
00343         } else {
00344             if (next_hop) {
00345                 *next_hop = dest;
00346             }
00347             return cost_direct;
00348         }
00349     }
00350 }
00351 
00352 /* Called by thread_routing.c as a result of updates to routing table - allows
00353  * leader to monitor a router being available (having a finite route cost).
00354  * Possible values for cost are 1-15, or 0 meaning infinite.
00355  */
00356 static void thread_router_link_changed(thread_info_t *thread_info, uint8_t router_id, uint8_t cost, int8_t interface_id)
00357 {
00358     /* Convert cost to scale to 0 (= cost 1) to 15 (= cost infinite), and place in bottom 4 bits of metric */
00359     uint8_t metric = ((unsigned) cost - 1) & 0xf;
00360 
00361     uint16_t router_addr_16 = thread_router_addr_from_id(router_id);
00362     uint8_t router_ip_addr[16];
00363     thread_addr_write_mesh_local_16(router_ip_addr, router_addr_16, thread_info);
00364 
00365     /* Leave upper (preference) bits of metric untouched */
00366     ipv6_route_table_modify_router_metric(interface_id, router_ip_addr, ROUTE_THREAD_BORDER_ROUTER, 0xf0, metric);
00367 
00368     /* Also tell the leader, who's monitoring which are available */
00369     thread_leader_service_router_state_changed(thread_info, router_id, cost != 0, interface_id);
00370 
00371 }
00372 
00373 static void set_fast_route_entry(thread_info_t *thread, thread_router_id_t dest, uint8_t value, thread_route_cost_t cost)
00374 {
00375     thread->routing.fast_route_table[dest] = value;
00376     thread_router_link_changed(thread, dest, cost, thread->interface_id);
00377 }
00378 
00379 /* Returns true if a change relevant to MLE Trickle has occurred */
00380 static bool thread_update_fast_route(thread_info_t *thread, thread_router_id_t dest)
00381 {
00382     thread_routing_info_t *routing = &thread->routing;
00383 
00384     if (routing->fast_route_table[dest] == FAST_ROUTE_INVALID_ID) {
00385         return false;
00386     }
00387 
00388     /* Trickle only cares if routes come or go, not if they change */
00389     bool change = false;
00390     thread_router_id_t next_hop;
00391     thread_route_cost_t cost = thread_compute_route_cost(routing, dest, &next_hop);
00392     if (cost == THREAD_COST_INFINITE) {
00393         if (routing->fast_route_table[dest] != FAST_ROUTE_NO_ROUTE) {
00394             change = true;
00395         }
00396 
00397         set_fast_route_entry(thread, dest, FAST_ROUTE_NO_ROUTE, THREAD_COST_INFINITE);
00398     } else {
00399         if (routing->fast_route_table[dest] == FAST_ROUTE_NO_ROUTE) {
00400             change = true;
00401         }
00402 
00403         set_fast_route_entry(thread, dest, next_hop, cost);
00404     }
00405 
00406     return change;
00407 }
00408 
00409 /* Rescan the neighbour list to generate the overall routing table. "id_valid"
00410  * fields are always live - this updates the other fields.
00411  */
00412 static void thread_update_fast_route_table(thread_info_t *thread)
00413 {
00414     bool change = false;
00415 
00416     for (thread_router_id_t id = 0; id < N_THREAD_ROUTERS; id++) {
00417         change |= thread_update_fast_route(thread, id);
00418     }
00419 
00420     if (change) {
00421         trickle_inconsistent_heard(&thread->routing.mle_advert_timer, &thread_mle_advert_trickle_params);
00422     }
00423 }
00424 
00425 void thread_routing_update_id_set(protocol_interface_info_entry_t *cur, uint8_t seq, const uint8_t *id_mask)
00426 {
00427     thread_info_t *thread = cur->thread_info;
00428     thread_routing_info_t *routing = &thread->routing;
00429     bool change = false;
00430 
00431     if (!router_id_sequence_is_greater(routing, seq)) {
00432         return;
00433     }
00434     routing->router_id_sequence = seq;
00435     routing->router_id_sequence_valid = true;
00436 
00437     for (thread_router_id_t i = 0; i < N_THREAD_ROUTERS; i++) {
00438         if (bit_test(id_mask, i)) {
00439             if (routing->fast_route_table[i] == FAST_ROUTE_INVALID_ID) {
00440                 /* Won't have any route info for this new router ID, but may have
00441                  * some existing link quality data from a handshake. Set
00442                  * initial route to direct, if we think we can hear it.
00443                  */
00444                 thread_route_cost_t cost = thread_get_neighbour_router_cost(routing, i);
00445                 if (cost == THREAD_COST_INFINITE) {
00446                     set_fast_route_entry(thread, i, FAST_ROUTE_NO_ROUTE, THREAD_COST_INFINITE);
00447                 } else {
00448                     set_fast_route_entry(thread, i, i, cost);
00449                     change = true;
00450                 }
00451                 tr_info("Add router (ID: %d)", i);
00452             }
00453         } else {
00454             if (routing->fast_route_table[i] != FAST_ROUTE_INVALID_ID) {
00455                 if (routing->fast_route_table[i] != FAST_ROUTE_NO_ROUTE) {
00456                     change = true;
00457                 }
00458                 set_fast_route_entry(thread, i, FAST_ROUTE_INVALID_ID, THREAD_COST_INFINITE);
00459                 tr_info("Remove router (ID: %d)", i);
00460                 thread_nd_flush_neighbour_cache_for_short_addr(cur, thread_router_addr_from_id(i), true);
00461                 thread_routing_remove_link(cur, thread_router_addr_from_id(i));
00462                 thread_delete_route_entry_by_id(thread, i);
00463             }
00464         }
00465     }
00466 
00467     /* Transitions from invalid->finite or finite->invalid must kick timer */
00468     if (change) {
00469         trickle_inconsistent_heard(&routing->mle_advert_timer, &thread_mle_advert_trickle_params);
00470     }
00471 }
00472 
00473 void thread_routing_force_next_hop(protocol_interface_info_entry_t *cur, uint8_t id_seq, const uint8_t *id_mask, thread_router_id_t next_hop_id)
00474 {
00475     /*
00476      * Called when we become a router, to make our original parent be
00477      * the initial path to all routers.
00478      *
00479      * Do this by creating and processing a fake advertisement from the
00480      * next hop. (We assume we have no existing routing information, so
00481      * it wins and ends up being our route to everywhere). Real routing
00482      * information, either from other routers or the one we're faking,
00483      * will then take over later.
00484      */
00485     uint8_t route_data[64];
00486     uint8_t *ptr = route_data;
00487     thread_router_id_t my_router_id = thread_router_id_from_addr(mac_helper_mac16_address_get(cur));
00488 
00489     for (thread_router_id_t r = 0; r < N_THREAD_ROUTERS; r++) {
00490         if (!bit_test(id_mask, r)) {
00491             continue;
00492         }
00493 
00494         if (r == my_router_id) {
00495             // It has a bad link to us
00496             *ptr++ = (QUALITY_2dB << ROUTE_DATA_OUT_SHIFT) | (QUALITY_2dB << ROUTE_DATA_IN_SHIFT) | thread_link_quality_to_cost(QUALITY_2dB);
00497         } else if (r == next_hop_id) {
00498             // It reports itself correctly
00499             *ptr++ = ROUTE_DATA_OURSELF;
00500         } else {
00501             // It has a maximum-length route to every other router (and no direct link)
00502             *ptr++ = (QUALITY_BAD << ROUTE_DATA_OUT_SHIFT) | (QUALITY_BAD << ROUTE_DATA_IN_SHIFT) | (THREAD_MAX_ROUTE_COST - thread_link_quality_to_cost(QUALITY_2dB));
00503         }
00504     }
00505 
00506     if (thread_routing_add_link(cur, thread_router_addr_from_id(next_hop_id), 4 /* dB (bad) */,
00507                                 id_seq, id_mask, route_data, false)) {
00508         tr_warn("Function thread_routing_force_next_hop() failed");
00509     }
00510 }
00511 
00512 /* We leave it to the caller to give us the dB link margin Thread wants.
00513  *
00514  * Getting that will be hardware dependent - new RF API needed...
00515  */
00516 
00517 static thread_router_link_t *thread_routing_update_link_margin_internal(thread_info_t *thread,
00518                                                                         uint16_t sender,
00519                                                                         uint8_t link_margin_db)
00520 {
00521     thread_router_id_t sender_id = thread_router_id_from_addr(sender);
00522 
00523     /* Find the sender in our Link Set - creating an entry if necessary */
00524     thread_router_link_t *neighbour = thread_get_neighbour_router_by_id(&thread->routing, sender_id);
00525     if (!neighbour) {
00526         neighbour = ns_dyn_mem_alloc(sizeof * neighbour);
00527         if (!neighbour) {
00528             return NULL;
00529         }
00530         neighbour->router_id = sender_id;
00531         neighbour->link_margin = link_margin_db << THREAD_LINK_MARGIN_SCALING;
00532         neighbour->incoming_quality = thread_link_margin_to_quality(neighbour->link_margin);
00533         neighbour->outgoing_quality = QUALITY_BAD;
00534         neighbour->outgoing_quality_known = false;
00535         neighbour->as_good = false;
00536         ns_list_add_to_end(&thread->routing.link_set, neighbour);
00537         trickle_inconsistent_heard(&thread->routing.mle_advert_timer, &thread_mle_advert_trickle_params); //Reset Trigle when learn new link
00538     } else {
00539         /* Exponentially weighted moving average, weighted by THREAD_LINK_MARGIN_SCALING */
00540         neighbour->link_margin = neighbour->link_margin + link_margin_db - (neighbour->link_margin >> THREAD_LINK_MARGIN_SCALING);
00541         neighbour->incoming_quality = link_margin_to_quality_with_hysteresis(neighbour->link_margin, (thread_link_quality_e) neighbour->incoming_quality);
00542     }
00543     neighbour->age = 0;
00544 
00545     return neighbour;
00546 }
00547 
00548 int_fast8_t thread_routing_update_link_margin(protocol_interface_info_entry_t *cur,
00549                                               uint16_t sender,
00550                                               uint8_t link_margin_db,
00551                                               uint8_t outgoing_link_margin_db)
00552 {
00553     thread_info_t *thread = cur->thread_info;
00554     /* Sanity check that the source is a Thread router */
00555     if (!thread || !thread_is_router_addr(sender)) {
00556         return -2;
00557     }
00558 
00559     tr_debug("New margin info for %04x: in=%d, out=%d", sender, link_margin_db, outgoing_link_margin_db);
00560 
00561     /* We record link quality info even if we're not currently a router - we can
00562      * use the info when we become one, and as part of the decision about
00563      * whether to become one.
00564      */
00565 
00566     thread_router_link_t *neighbour = thread_routing_update_link_margin_internal(thread, sender, link_margin_db);
00567     if (!neighbour) {
00568         return -3;
00569     }
00570 
00571     /* We use the outgoing link margin provided here only if we haven't ever
00572      * heard an actual Route TLV quality report from the neighbour. This is
00573      * intended for "secondary" info, derived from RSSI TLVs to bootstrap.
00574      */
00575     if (!neighbour->outgoing_quality_known) {
00576         neighbour->outgoing_quality = thread_link_margin_to_quality(outgoing_link_margin_db);
00577     }
00578 
00579     thread_update_fast_route_table(thread);
00580 
00581     return 0;
00582 }
00583 
00584 int_fast8_t thread_routing_force_link_margin(protocol_interface_info_entry_t *cur,
00585                                              uint16_t addr,
00586                                              uint8_t link_margin_db)
00587 {
00588     thread_info_t *thread = cur->thread_info;
00589     if (!thread || !cur->mac_parameters || !thread_is_router_addr(addr)) {
00590         return -2;
00591     }
00592 
00593     thread_router_id_t sender_id = thread_router_id_from_addr(addr);
00594     thread_router_link_t *neighbour = thread_get_neighbour_router_by_id(&thread->routing, sender_id);
00595     if (!neighbour) {
00596         return -3;
00597     }
00598 
00599     tr_debug("Forcing link margin for %04x: in=%d", addr, link_margin_db);
00600 
00601     neighbour->link_margin = link_margin_db << THREAD_LINK_MARGIN_SCALING;
00602     neighbour->incoming_quality = thread_link_margin_to_quality(neighbour->link_margin);
00603 
00604     thread_update_fast_route_table(thread);
00605 
00606     return 0;
00607 }
00608 
00609 int_fast8_t thread_routing_add_link(protocol_interface_info_entry_t *cur,
00610                                     uint16_t sender, uint8_t link_margin_db,
00611                                     uint8_t id_seq,
00612                                     const uint8_t *id_mask,
00613                                     const uint8_t *route_data,
00614                                     bool is_static)
00615 {
00616     thread_info_t *thread = cur->thread_info;
00617     if (!thread) {
00618         return -2;
00619     }
00620 
00621     /* Update master Router ID Set */
00622     thread_routing_update_id_set(cur, id_seq, id_mask);
00623 
00624     /* Sanity check that the source is a Thread router */
00625     if (!thread_is_router_addr(sender)) {
00626         return -2;
00627     }
00628 
00629     /* Even if not currently a router, worth tracking incoming link margin in case we become one */
00630     thread_router_link_t *neighbour = thread_routing_update_link_margin_internal(thread, sender, link_margin_db);
00631     if (!neighbour) {
00632         return -3;
00633     }
00634 
00635     /* Now check that we're a router - if not, we don't bother with anything further */
00636     if (!thread_is_router_addr(mac_helper_mac16_address_get(cur))) {
00637         return 0;
00638     }
00639 
00640     thread_router_id_t sender_id = thread_router_id_from_addr(sender);
00641     thread_router_id_t my_router_id = thread_router_id_from_addr(mac_helper_mac16_address_get(cur));
00642 
00643     neighbour->age = is_static ? LINK_AGE_STATIC : 0;
00644 
00645     /* We have to check its quality report for us first - need to have
00646      * this information before making routing decisions.
00647      */
00648     const uint8_t *ptr = route_data;
00649     for (thread_router_id_t r = 0; r < N_THREAD_ROUTERS; r++) {
00650         uint8_t byte;
00651         bool router_in_mask = bit_test(id_mask, r);
00652 
00653         if (router_in_mask) {
00654             byte = *ptr++;
00655         } else {
00656             byte = (QUALITY_BAD << ROUTE_DATA_OUT_SHIFT) | (QUALITY_BAD << ROUTE_DATA_IN_SHIFT) | THREAD_COST_INFINITE;
00657         }
00658 
00659         if (r == my_router_id) {
00660             neighbour->outgoing_quality_known = router_in_mask;
00661             neighbour->outgoing_quality = (byte & ROUTE_DATA_IN_MASK) >> ROUTE_DATA_IN_SHIFT;
00662             break;
00663         }
00664     }
00665 
00666     /* Compute Thread REED downgrade condition - does this router have as good or better quality links
00667      * to all Routers for which we have two-way link quality 2 (10dB) or better?
00668      */
00669     neighbour->as_good = true;
00670     ptr = route_data;
00671     for (thread_router_id_t r = 0; r < N_THREAD_ROUTERS; r++) {
00672         uint8_t byte;
00673         bool router_in_mask = bit_test(id_mask, r);
00674 
00675         if (router_in_mask) {
00676             byte = *ptr++;
00677         } else {
00678             byte = (QUALITY_BAD << ROUTE_DATA_OUT_SHIFT) | (QUALITY_BAD << ROUTE_DATA_IN_SHIFT) | THREAD_COST_INFINITE;
00679         }
00680 
00681         if (r == sender_id) {
00682             continue;
00683         }
00684 
00685         thread_router_link_t *other_neighbour = thread_get_neighbour_router_by_id(&thread->routing, r);
00686         if (!other_neighbour) {
00687             continue;
00688         }
00689 
00690         thread_link_quality_e our_quality_to_other_neighbour = thread_neighbour_router_quality(other_neighbour);
00691         if (our_quality_to_other_neighbour < QUALITY_10dB) {
00692             continue;
00693         }
00694         thread_link_quality_e neighbours_incoming_quality_to_other_neighbour = (thread_link_quality_e)((byte & ROUTE_DATA_IN_MASK) >> ROUTE_DATA_IN_SHIFT);
00695         thread_link_quality_e neighbours_outgoing_quality_to_other_neighbour = (thread_link_quality_e)((byte & ROUTE_DATA_OUT_MASK) >> ROUTE_DATA_OUT_SHIFT);
00696         thread_link_quality_e neighbours_quality_to_other_neighbour = thread_quality_combine(neighbours_incoming_quality_to_other_neighbour,
00697                                                                                              neighbours_outgoing_quality_to_other_neighbour);
00698         if (neighbours_quality_to_other_neighbour < our_quality_to_other_neighbour) {
00699             neighbour->as_good = false;
00700             break;
00701         }
00702     }
00703 
00704     /* Now go through and update routes based on its data */
00705     for (thread_router_id_t r = 0; r < N_THREAD_ROUTERS; r++) {
00706         uint8_t byte;
00707 
00708         /* If a router isn't in its ID set (but remains in ours), we treat
00709          * it as if it's saying "no route"+"quality bad".
00710          */
00711         if (bit_test(id_mask, r)) {
00712             byte = *route_data++;
00713         } else {
00714             byte = (QUALITY_BAD << ROUTE_DATA_OUT_SHIFT) | (QUALITY_BAD << ROUTE_DATA_IN_SHIFT) | THREAD_COST_INFINITE;
00715         }
00716 
00717         /* Only _after_ consuming route data do we skip invalid IDs */
00718         if (thread->routing.fast_route_table[r] == FAST_ROUTE_INVALID_ID) {
00719             continue;
00720         }
00721 
00722         if (r == sender_id || r == my_router_id) {
00723             continue;
00724         }
00725 
00726         thread_route_t *route_entry = thread_get_route_entry_by_id(&thread->routing, r);
00727         thread_route_cost_t cost_reported = byte & ROUTE_DATA_COST_MASK;
00728         if (cost_reported == 0) {
00729             /* If sender was our next hop to r, but it no longer has a route */
00730             if (route_entry && route_entry->next_hop == sender_id) {
00731                 /* Really delete the route? I guess the model in the spec
00732                  * doesn't leave us with the state info to choose an alternative
00733                  * immediately, so we do have to wait for more adverts...
00734                  */
00735                 tr_debug("Delete Route by Cost Report: NH=%d dest=%d", route_entry->next_hop, route_entry->destination);
00736                 ns_list_remove(&thread->routing.route_set, route_entry);
00737                 ns_dyn_mem_free(route_entry);
00738             }
00739         } else {
00740             /* If we have no existing multihop route, or if this is our
00741              * existing multihop route, or it's better than our existing one */
00742             if (route_entry == NULL ||
00743                     route_entry->next_hop == sender_id ||
00744                     cost_less(thread_link_cost_sum(thread_neighbour_router_cost(neighbour), cost_reported),
00745                               thread_link_cost_sum(thread_get_neighbour_router_cost(&thread->routing, route_entry->next_hop), route_entry->route_cost))) {
00746                 if (!route_entry) {
00747                     route_entry = ns_dyn_mem_alloc(sizeof * route_entry);
00748                     if (!route_entry) {
00749                         continue;
00750                     }
00751                     route_entry->destination = r;
00752                     ns_list_add_to_end(&thread->routing.route_set, route_entry);
00753                 } else {
00754                     tr_debug("Update Old %d D, %d NH, %d C", route_entry->destination, route_entry->next_hop, route_entry->route_cost);
00755                 }
00756                 route_entry->next_hop = sender_id;
00757                 route_entry->route_cost = cost_reported;
00758             }
00759         }
00760     }
00761 
00762     thread_update_fast_route_table(thread);
00763 
00764     return 0;
00765 }
00766 
00767 static void delete_link(thread_info_t *thread, thread_router_link_t *link)
00768 {
00769     thread_router_id_t id = link->router_id;
00770     thread_routing_info_t *routing = &thread->routing;
00771 
00772     tr_debug("delete_link: router: %x", thread_router_addr_from_id(link->router_id));
00773 
00774     /* Remove entry from the link set */
00775     ns_list_remove(&routing->link_set, link);
00776     ns_dyn_mem_free(link);
00777 
00778     /* Remove all routing entries for which that link was the next hop */
00779     ns_list_foreach_safe(thread_route_t, route_entry, &routing->route_set) {
00780         if (route_entry->next_hop == id) {
00781             ns_list_remove(&routing->route_set, route_entry);
00782             ns_dyn_mem_free(route_entry);
00783         }
00784     }
00785     thread_update_fast_route_table(thread);
00786 }
00787 
00788 int_fast8_t thread_routing_remove_link(protocol_interface_info_entry_t *cur,
00789                                        uint16_t sender)
00790 {
00791     thread_info_t *thread = cur->thread_info;
00792     /* Sanity check that the source is a Thread router */
00793     if (!thread || !thread_is_router_addr(sender)) {
00794         return -2;
00795     }
00796 
00797     thread_router_id_t sender_id = thread_router_id_from_addr(sender);
00798     thread_router_link_t *neighbour = thread_get_neighbour_router_by_id(&thread->routing, sender_id);
00799     if (!neighbour) {
00800         return -1;
00801     }
00802 
00803     delete_link(thread, neighbour);
00804 
00805     return 0;
00806 }
00807 
00808 uint8_t thread_routing_get_route_data_size(protocol_interface_info_entry_t *cur)
00809 {
00810     uint_fast8_t len = 0;
00811     thread_info_t *thread = cur->thread_info;
00812     if (!thread || !thread->routing.router_id_sequence_valid) {
00813         return 0;
00814     }
00815 
00816     for (thread_router_id_t r = 0; r < N_THREAD_ROUTERS; r++) {
00817         if (thread->routing.fast_route_table[r] != FAST_ROUTE_INVALID_ID) {
00818             len++;
00819         }
00820     }
00821 
00822     return len;
00823 }
00824 
00825 uint_fast8_t thread_routing_cost_get_by_router_id(thread_routing_info_t *routing, uint8_t routerId)
00826 {
00827     return thread_compute_route_cost(routing, routerId, NULL);
00828 }
00829 
00830 int_fast8_t thread_routing_get_route_data(protocol_interface_info_entry_t *cur,
00831                                           uint8_t *id_seq,
00832                                           uint8_t *id_mask,
00833                                           uint8_t *data,
00834                                           uint8_t *len_out)
00835 {
00836     uint8_t len = 0;
00837     thread_info_t *thread = cur->thread_info;
00838     if (!thread || !thread->routing.router_id_sequence_valid) {
00839         return -1;
00840     }
00841 
00842     uint16_t mac16 = mac_helper_mac16_address_get(cur);
00843 
00844     *id_seq = thread->routing.router_id_sequence;
00845     memset(id_mask, 0, (N_THREAD_ROUTERS + 7) / 8);
00846 
00847     for (thread_router_id_t r = 0; r < N_THREAD_ROUTERS; r++) {
00848         uint8_t val;
00849 
00850         if (thread->routing.fast_route_table[r] == FAST_ROUTE_INVALID_ID) {
00851             continue;
00852         }
00853 
00854         bit_set(id_mask, r);
00855 
00856         if (thread_router_addr_from_id(r) == mac16) {
00857             val = ROUTE_DATA_OURSELF;
00858         } else {
00859             thread_router_link_t *link = thread_get_neighbour_router_by_id(&thread->routing, r);
00860             if (link) {
00861                 val = (link->outgoing_quality << ROUTE_DATA_OUT_SHIFT)
00862                       | (link->incoming_quality << ROUTE_DATA_IN_SHIFT);
00863             } else {
00864                 val = (QUALITY_BAD << ROUTE_DATA_OUT_SHIFT)
00865                       | (QUALITY_BAD << ROUTE_DATA_IN_SHIFT);
00866             }
00867 
00868             val |= thread_compute_route_cost(&thread->routing, r, NULL);
00869         }
00870 
00871         *data++ = val;
00872         len++;
00873     }
00874 
00875     *len_out = len;
00876 
00877     return 0;
00878 }
00879 
00880 void thread_routing_init(thread_routing_info_t *routing)
00881 {
00882     ns_list_init(&routing->route_set);
00883     ns_list_init(&routing->link_set);
00884     thread_routing_reset(routing);
00885 }
00886 
00887 void thread_routing_reset(thread_routing_info_t *routing)
00888 {
00889     thread_routing_free(routing);
00890     routing->router_id_sequence_valid = false;
00891     routing->networkIdTimeout = NETWORK_ID_TIMEOUT;
00892     memset(routing->fast_route_table, FAST_ROUTE_INVALID_ID, sizeof routing->fast_route_table);
00893     trickle_start(&routing->mle_advert_timer, &thread_mle_advert_trickle_params);
00894 }
00895 
00896 void thread_routing_free(thread_routing_info_t *routing)
00897 {
00898     ns_list_foreach_safe(thread_route_t, route_entry, &routing->route_set) {
00899         ns_list_remove(&routing->route_set, route_entry);
00900         ns_dyn_mem_free(route_entry);
00901     }
00902 
00903     ns_list_foreach_safe(thread_router_link_t, link_entry, &routing->link_set) {
00904         ns_list_remove(&routing->link_set, link_entry);
00905         ns_dyn_mem_free(link_entry);
00906     }
00907 }
00908 
00909 void thread_routing_activate(thread_routing_info_t *routing)
00910 {
00911     trickle_inconsistent_heard(&routing->mle_advert_timer, &thread_mle_advert_trickle_params);
00912     routing->activated = true;
00913     routing->networkFragmentationTimer = 0;
00914 }
00915 
00916 void thread_routing_deactivate(thread_routing_info_t *routing)
00917 {
00918     thread_routing_reset(routing);
00919     routing->activated = false;
00920 }
00921 
00922 /* ticks is in 100ms units, I think */
00923 /* Return true if we want to send an MLE advertisement */
00924 bool thread_routing_timer(thread_info_t *thread, uint8_t ticks)
00925 {
00926     thread_routing_info_t *routing = &thread->routing;
00927 
00928     if (!routing->activated) {
00929         return false;
00930     }
00931 
00932     ns_list_foreach_safe(thread_router_link_t, link, &routing->link_set) {
00933         if (link->age == LINK_AGE_STATIC) {
00934             continue;
00935         }
00936 
00937         link->age += ticks;
00938         if (link->age > MAX_LINK_AGE) {
00939             delete_link(thread, link);
00940         }
00941     }
00942 
00943     return trickle_timer(&routing->mle_advert_timer, &thread_mle_advert_trickle_params, ticks);
00944 }
00945 
00946 /* This is experimental and is testing if we can improve long topology networks to be more stable without
00947  * resetting the trickle every time we hear inconsistency.
00948  * This speeds up next advertisement when connection restored
00949  *
00950  * Solution proposal 2:
00951  * turn on consistency checking, treat leader data changes as inconsistent, and matching leader data
00952  * as consistent if we've sent an advertisement recently.
00953  * Needs specification update. Does cause more resetting of trickle.
00954  *
00955  */
00956 
00957 //
00958 //
00959 
00960 static void thread_trickle_accelerate(trickle_t *t, const trickle_params_t *params, uint16_t ticks)
00961 {
00962     trickle_time_t new_time = t->now + ticks;
00963 
00964     /* Catch overflow */
00965     if (new_time < t->now) {
00966         new_time = TRICKLE_TIME_MAX;
00967     }
00968 
00969     if (new_time < t->t) {
00970         // We must speed up this so that next trigger happens before this time
00971         t->now = t->t - new_time;
00972     }
00973     if (t->now > t->t) {
00974         // if now is larger than t move t to trigger event again during this period
00975         t->t = t->now + randLIB_get_random_in_range(0, params->Imin / 2);
00976     }
00977 }
00978 
00979 void thread_routing_trickle_advance(thread_routing_info_t *routing, uint16_t ticks)
00980 {
00981     trickle_t *t = &routing->mle_advert_timer;
00982 
00983     if (!trickle_running(t, &thread_mle_advert_trickle_params)) {
00984         return;
00985     }
00986 
00987     if ((t->t > t->now) && (t->t - t->now < ticks)) {
00988         /* advance trickle elapsing time by number of ticks */
00989         t->t = t->t + ticks - (t->t - t->now);
00990         tr_debug("trickle advanced to %d, now %d ", t->t, t->now);
00991     }
00992 }
00993 
00994 // This functions speeds up next advertisement depending on the disconnect period to leader
00995 void thread_routing_leader_connection_validate(thread_info_t *thread, uint16_t disconnect_period)
00996 {
00997     thread_routing_info_t *routing = &thread->routing;
00998 
00999     if (!routing->activated) {
01000         return;
01001     }
01002     //If disconnect period is about 60 seconds make sure next advertisement happens before 70 second mark
01003     if (disconnect_period < NETWORK_ID_SPEEDUP) {
01004         return;
01005     }
01006     if (disconnect_period > NETWORK_ID_SPEEDUP_MAX) {
01007         tr_debug("Leader restored:accelerate reset: %d", disconnect_period);
01008         trickle_inconsistent_heard(&routing->mle_advert_timer, &thread_mle_advert_trickle_params);
01009     } else {
01010         tr_debug("Leader restored:accelerate: %d", disconnect_period);
01011         thread_trickle_accelerate(&routing->mle_advert_timer, &thread_mle_advert_trickle_params, 100);// 10 second with 100ms tics
01012     }
01013 }
01014 
01015 static bool thread_forwardable_address_fn(const protocol_interface_info_entry_t *cur, addrtype_t addr_type, const uint8_t *address)
01016 {
01017     (void) cur;
01018     if (addr_type != ADDR_802_15_4_SHORT ) {
01019         return false;
01020     }
01021 
01022     if (addr_check_broadcast(address, addr_type) == 0) {
01023         return false;
01024     }
01025 
01026     return true;
01027 }
01028 
01029 static bool thread_address_map_fn(protocol_interface_info_entry_t *cur, addrtype_t *addr_type, uint8_t *address)
01030 {
01031     /* Don't touch addresses other than short */
01032     if (*addr_type != ADDR_802_15_4_SHORT ) {
01033         return true;
01034     }
01035 
01036     /* Anything with maximum router ID is anycast - others are normal unmapped unicast */
01037     uint16_t addr16 = common_read_16_bit(address + 2);
01038     if (thread_router_id_from_addr(addr16) != N_THREAD_ROUTERS - 1) {
01039         return true;
01040     }
01041 
01042     /* If the ND mapping function fails, drop the packet */
01043     if (thread_nd_map_anycast_address(cur, &addr16) < 0) {
01044         return false;
01045     }
01046 
01047     /* Update the address */
01048     common_write_16_bit(addr16, address + 2);
01049     return true;
01050 }
01051 
01052 static bool thread_header_needed_fn(const protocol_interface_info_entry_t *cur, const buffer_t *buf)
01053 {
01054     /* Never mesh headers on broadcasts/multicasts */
01055     if (addr_check_broadcast(buf->dst_sa .address , buf->dst_sa .addr_type ) == 0) {
01056         return false;
01057     }
01058     /* We have no use for long addresses in mesh headers */
01059     if (buf->dst_sa .addr_type  != ADDR_802_15_4_SHORT  || buf->src_sa .addr_type  != ADDR_802_15_4_SHORT ) {
01060         return false;
01061     }
01062 
01063     /* Don't need a mesh header if travelling between a router and its child */
01064     uint16_t src = common_read_16_bit(buf->src_sa .address  + 2);
01065     uint16_t dst = common_read_16_bit(buf->dst_sa .address  + 2);
01066     if (src == thread_router_addr_from_addr(dst) || dst == thread_router_addr_from_addr(src)) {
01067         return false;
01068     }
01069 
01070     /* Don't need a mesh header if we are routing directly to a neighbor router
01071        Possibly unsafe if routing info changes before it reaches the transmit stage? */
01072     if (thread_i_am_router(cur) && thread_is_router_addr(dst)) {
01073         thread_router_id_t id = thread_router_id_from_addr(dst);
01074         /* Direct routing is indicated by the next hop
01075            in fast_route_table being the router itself */
01076         if (cur->thread_info->routing.fast_route_table[id] == id) {
01077             return false;
01078         }
01079     }
01080 
01081     return true;
01082 }
01083 
01084 
01085 static mesh_callbacks_t thread_routing_mesh_callbacks = {
01086     .first_hop = thread_first_hop_fn,
01087     .route = thread_route_fn,
01088     .header_needed = thread_header_needed_fn,
01089     .forwardable_address = thread_forwardable_address_fn,
01090     .address_map = thread_address_map_fn,
01091 };
01092 
01093 void thread_routing_set_mesh_callbacks(protocol_interface_info_entry_t *cur)
01094 {
01095     cur->mesh_callbacks = &thread_routing_mesh_callbacks;
01096     mesh_all_addresses_unicast(true);
01097 }
01098 
01099 /* Return value = number of neighbours with quality 10dB or better ("set M")
01100  * *as_good     = number of neighbours with as good or better quality links to all routers in set M
01101  *
01102  * (Note, these numbers are not calculated at exactly the same time, so could be a slight mismatch...)
01103  */
01104 uint_fast8_t thread_routing_count_neighbours_for_downgrade(thread_routing_info_t *routing, uint_fast8_t *as_good)
01105 {
01106     uint_fast8_t linkCnt = 0;
01107     *as_good = 0;
01108     thread_link_quality_e linkQuality;
01109     ns_list_foreach_safe(thread_router_link_t, link, &routing->link_set) {
01110         linkQuality = thread_neighbour_router_quality(link);
01111         if (linkQuality >= QUALITY_10dB) {
01112             linkCnt++;
01113         }
01114         if (link->as_good) {
01115             (*as_good)++;
01116         }
01117     }
01118 
01119     return linkCnt;
01120 }
01121 
01122 uint_fast8_t thread_routing_count_active_routers(thread_routing_info_t *routing)
01123 {
01124     uint_fast8_t activeRouterCnt = 0;
01125     for (thread_router_id_t i = 0; i < N_THREAD_ROUTERS; i++) {
01126 
01127         if (routing->fast_route_table[i] != FAST_ROUTE_INVALID_ID) {
01128             activeRouterCnt++;
01129         }
01130     }
01131 
01132     return activeRouterCnt;
01133 }
01134 
01135 uint_fast8_t thread_routing_count_active_routers_from_mask(const uint8_t *id_mask)
01136 {
01137     uint_fast8_t activeRouterCnt = 0;
01138     for (uint_fast8_t i = 0; i < 8; i++) {
01139         activeRouterCnt += common_count_bits(id_mask[i]);
01140     }
01141     return activeRouterCnt;
01142 }
01143 
01144 #endif //HAVE_THREAD_ROUTER