thread_routing.h

00001 /*
00002  * Copyright (c) 2014-2017, 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 #ifndef THREAD_ROUTING_H_
00030 #define THREAD_ROUTING_H_
00031 
00032 #include "NWK_INTERFACE/Include/protocol.h"
00033 #include <ns_list.h>
00034 #ifndef UINT_FAST12_MAX
00035 typedef uint_fast16_t   uint_fast12_t;
00036 #define UINT_FAST12_MAX UINT_FAST16_MAX
00037 #endif
00038 
00039 #include "Service_Libs/Trickle/trickle.h"
00040 
00041 struct thread_info_s;
00042 
00043 #define MAX_ROUTER_ID           62
00044 #define N_THREAD_ROUTERS        64
00045 #define THREAD_ROUTER_ID_BITS   6
00046 #define THREAD_ROUTER_MASK      0xFC00
00047 #define THREAD_ROUTER_SHIFT     10
00048 #define THREAD_CHILD_MASK       0x03FF
00049 #define THREAD_ROUTER_IDX       0
00050 
00051 typedef uint_fast8_t thread_router_id_t;
00052 
00053 #define THREAD_QUALITY_BITS     2
00054 #define THREAD_COST_BITS        4
00055 #define THREAD_COST_INFINITE    0
00056 #define THREAD_MAX_ROUTE_COST   15
00057 
00058 /* Scaled link margin */
00059 #define THREAD_LINK_MARGIN_BITS     12
00060 #define THREAD_LINK_MARGIN_SCALING  3   /* For 1/8 exponential moving average weighting */
00061 
00062 #if THREAD_LINK_MARGIN_BITS == 12
00063 typedef uint_fast12_t thread_link_margin_t;
00064 #define THREAD_LINK_MARGIN_MAX UINT_FAST12_MAX
00065 #endif
00066 
00067 /* I want to use uint_fast4_t - create it if it doesn't exist */
00068 #ifndef UINT_FAST4_MAX
00069 typedef uint_fast8_t    uint_fast4_t;
00070 #define UINT_FAST4_MAX  UINT_FAST8_MAX
00071 #endif
00072 typedef uint_fast4_t thread_route_cost_t;
00073 
00074 typedef enum {
00075     QUALITY_20dB = 3,
00076     QUALITY_10dB = 2,
00077     QUALITY_2dB = 1,
00078     QUALITY_BAD = 0,
00079 } thread_link_quality_e;
00080 
00081 /* The draft-kelsey-thread-routing-00 Link Set */
00082 /* XXX - probably don't need this - put it into mle_neigh_table? */
00083 typedef struct thread_router_link_s {
00084     unsigned router_id          : THREAD_ROUTER_ID_BITS;
00085     unsigned incoming_quality   : THREAD_QUALITY_BITS;
00086     unsigned outgoing_quality   : THREAD_QUALITY_BITS;
00087     unsigned link_margin        : THREAD_LINK_MARGIN_BITS;
00088     unsigned age                : 12; /* 100ms ticks, so good for ~2 hours */
00089     bool outgoing_quality_known : 1;
00090     bool as_good                : 1;
00091     ns_list_link_t link;
00092 } thread_router_link_t;
00093 
00094 /* The draft-kelsey-thread-routing-00 Route Set */
00095 typedef struct thread_route_s {
00096     unsigned destination        : THREAD_ROUTER_ID_BITS;
00097     unsigned next_hop           : THREAD_ROUTER_ID_BITS;
00098     unsigned route_cost         : THREAD_COST_BITS;     /* Cost according to next_hop - doesn't include our cost to next_hop */
00099     ns_list_link_t link;
00100 } thread_route_t;
00101 
00102 /* Fast routing table - also serves as the draft-kelsey-thread-routing-00 Router ID Set
00103  * Entries currently squeeze into 1 byte, making fast_route_table a 64-byte array
00104  *
00105  * "INVALID_ID" or not is always live info, as that's the master ID Set
00106  * storage. If ID is valid, the route decision is a cache generated from
00107  * route_set and link_set, and it needs to be kept up-to-date with
00108  * thread_update_fast_route_table() when those change.
00109  */
00110 #define FAST_ROUTE_INVALID_ID   0xFF
00111 #define FAST_ROUTE_NO_ROUTE     0xFE
00112 #if N_THREAD_ROUTERS > 0xFD
00113 #error "rework fast_route_table"
00114 #endif
00115 
00116 typedef struct thread_routing_info_s {
00117     NS_LIST_HEAD (thread_router_link_t, link) link_set;
00118     NS_LIST_HEAD (thread_route_t, link) route_set;
00119     uint_least8_t fast_route_table[N_THREAD_ROUTERS];
00120     bool activated;
00121     bool router_id_sequence_valid;
00122     uint8_t router_id_sequence;
00123     uint16_t networkFragmentationTimer;
00124     uint16_t networkIdTimeout; //!< timeout in seconds
00125     trickle_t mle_advert_timer;
00126 }
00127 thread_routing_info_t;
00128 
00129 #ifdef HAVE_THREAD
00130 
00131 /* See ns_types.h for explanation */
00132 NS_INLINE thread_router_id_t thread_router_id_from_addr(uint16_t addr);
00133 NS_INLINE uint16_t thread_router_addr_from_id(thread_router_id_t addr);
00134 NS_INLINE uint16_t thread_router_addr_from_addr(uint16_t addr);
00135 NS_INLINE bool thread_is_router_addr(uint16_t addr);
00136 NS_INLINE bool thread_addr_is_child(uint16_t a, uint16_t b);
00137 NS_INLINE bool thread_addr_is_equal_or_child(uint16_t a, uint16_t b);
00138 
00139 #if defined NS_ALLOW_INLINING || defined THREAD_ROUTING_FN
00140 #ifndef THREAD_ROUTING_FN
00141 #define THREAD_ROUTING_FN NS_INLINE
00142 #endif
00143 THREAD_ROUTING_FN thread_router_id_t thread_router_id_from_addr(uint16_t addr)
00144 {
00145     return addr >> THREAD_ROUTER_SHIFT;
00146 }
00147 
00148 THREAD_ROUTING_FN uint16_t thread_router_addr_from_id(thread_router_id_t addr)
00149 {
00150     return (uint_fast16_t) addr << THREAD_ROUTER_SHIFT;
00151 }
00152 
00153 THREAD_ROUTING_FN uint16_t thread_router_addr_from_addr(uint16_t addr)
00154 {
00155     return (addr & THREAD_ROUTER_MASK) | THREAD_ROUTER_IDX;
00156 }
00157 
00158 THREAD_ROUTING_FN bool thread_is_router_addr(uint16_t addr)
00159 {
00160     return (addr & ~ THREAD_ROUTER_MASK) == THREAD_ROUTER_IDX;
00161 }
00162 
00163 /* Return true if b is a child of a */
00164 THREAD_ROUTING_FN bool thread_addr_is_child(uint16_t a, uint16_t b)
00165 {
00166     if (thread_is_router_addr(b)) {
00167         return false;
00168     }
00169     return thread_router_addr_from_addr(b) == a;
00170 }
00171 
00172 /* Return true if b is equal to a, or b is a child of a */
00173 THREAD_ROUTING_FN bool thread_addr_is_equal_or_child(uint16_t a, uint16_t b)
00174 {
00175     return b == a || thread_addr_is_child(a, b);
00176 }
00177 #endif /* NS_ALLOW_INLINING || defined THREAD_ROUTING_FN */
00178 #endif // HAVE_THREAD
00179 
00180 #ifdef HAVE_THREAD_ROUTER
00181 
00182 bool thread_i_am_router(const protocol_interface_info_entry_t *cur);
00183 
00184 void thread_routing_init(thread_routing_info_t *routing);
00185 void thread_routing_reset(thread_routing_info_t *routing);
00186 void thread_routing_free(thread_routing_info_t *routing);
00187 void thread_routing_activate(thread_routing_info_t *routing);
00188 void thread_routing_deactivate(thread_routing_info_t *routing);
00189 bool thread_routing_timer(struct thread_info_s *thread, uint8_t ticks);
00190 void thread_routing_leader_connection_validate(struct thread_info_s *thread, uint16_t disconnect_period);
00191 void thread_routing_set_mesh_callbacks(protocol_interface_info_entry_t *cur);
00192 
00193 uint_fast8_t thread_routing_cost_get_by_router_id(thread_routing_info_t *routing , uint8_t routerId);
00194 bool router_id_sequence_is_greater(const thread_routing_info_t *routing, uint8_t seq);
00195 
00196 uint_fast8_t thread_routing_count_neighbours_for_downgrade(thread_routing_info_t *routing, uint_fast8_t *as_good);
00197 uint_fast8_t thread_routing_count_active_routers(thread_routing_info_t *routing);
00198 uint_fast8_t thread_routing_count_active_routers_from_mask(const uint8_t *id_mask);
00199 
00200 //Init
00201 void thread_routing_update_id_set(protocol_interface_info_entry_t *cur, uint8_t seq, const uint8_t *id_mask);
00202 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);
00203 
00204 int_fast8_t thread_routing_update_link_margin(protocol_interface_info_entry_t *cur,
00205         uint16_t sender,
00206         uint8_t link_margin_db,
00207         uint8_t outgoing_link_margin_db);
00208 int_fast8_t thread_routing_force_link_margin(protocol_interface_info_entry_t *cur,
00209         uint16_t addr,
00210         uint8_t link_margin_db);
00211 int_fast8_t thread_routing_add_link(protocol_interface_info_entry_t *cur,
00212                                     uint16_t sender, uint8_t link_margin_db,
00213                                     uint8_t id_seq,
00214                                     const uint8_t *id_mask,
00215                                     const uint8_t *route_data,
00216                                     bool is_static);
00217 int_fast8_t thread_routing_remove_link(protocol_interface_info_entry_t *cur,
00218                                        uint16_t sender);
00219 
00220 uint8_t thread_routing_get_route_data_size(protocol_interface_info_entry_t *cur);
00221 
00222 int_fast8_t thread_routing_get_route_data(protocol_interface_info_entry_t *cur,
00223         uint8_t *id_seq,
00224         uint8_t *id_mask,
00225         uint8_t *data,
00226         uint8_t *len_out);
00227 #else // HAVE_THREAD_ROUTER
00228 
00229 #define thread_i_am_router(cur) false
00230 #define thread_routing_init(routing)
00231 #define thread_routing_reset(routing)
00232 #define thread_routing_free(routing)
00233 #define thread_routing_activate(routing)
00234 #define thread_routing_deactivate(routing)
00235 #define thread_routing_timer(thread, ticks) false
00236 #define thread_routing_leader_connection_validate(thread, disconnect_period)
00237 #define thread_routing_set_mesh_callbacks(cur)
00238 #define thread_routing_cost_get_by_router_id(routing, routerId) (0)
00239 #define thread_routing_count_active_routers(routing) 0
00240 #define thread_routing_count_active_routers_from_mask(id_mask) 0
00241 #define thread_routing_update_id_set(cur, seq, id_mask)
00242 #define thread_routing_update_link_margin(cur, sender, link_margin_db, outgoing_link_margin_db) (-3)
00243 #define thread_routing_force_link_margin(cur, addr, link_margin_db) (-3)
00244 #define thread_routing_add_link(cur, sender, link_margin_db, id_seq, id_mask, route_data, is_static) (-2)
00245 #define thread_is_router_addr(addr) false
00246 #define thread_routing_remove_link(cur, sender) 0
00247 #define thread_routing_get_route_data_size(cur) 0
00248 #define thread_routing_get_route_data(cur,id_seq,id_mask,data,len_out) (0)
00249 #define thread_addr_is_equal_or_child(a, b) false
00250 #define thread_addr_is_child(a, b) false
00251 
00252 #endif // HAVE_THREAD_ROUTER
00253 
00254 #endif /* THREAD_ROUTING_H_ */