thread_routing.h

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 #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 // *INDENT-OFF* astyle
00085     unsigned router_id          : THREAD_ROUTER_ID_BITS;
00086     unsigned incoming_quality   : THREAD_QUALITY_BITS;
00087     unsigned outgoing_quality   : THREAD_QUALITY_BITS;
00088     unsigned link_margin        : THREAD_LINK_MARGIN_BITS;
00089 // *INDENT-ON*
00090     unsigned age                : 12; /* 100ms ticks, so good for ~2 hours */
00091     bool outgoing_quality_known : 1;
00092     bool as_good                : 1;
00093     ns_list_link_t link;
00094 } thread_router_link_t;
00095 
00096 /* The draft-kelsey-thread-routing-00 Route Set */
00097 typedef struct thread_route_s {
00098 // *INDENT-OFF* astyle
00099     unsigned destination     : THREAD_ROUTER_ID_BITS;
00100     unsigned next_hop        : THREAD_ROUTER_ID_BITS;
00101     unsigned route_cost      : THREAD_COST_BITS;     /* Cost according to next_hop - doesn't include our cost to next_hop */
00102 // *INDENT-ON* astyle
00103     ns_list_link_t link;
00104 } thread_route_t;
00105 
00106 /* Fast routing table - also serves as the draft-kelsey-thread-routing-00 Router ID Set
00107  * Entries currently squeeze into 1 byte, making fast_route_table a 64-byte array
00108  *
00109  * "INVALID_ID" or not is always live info, as that's the master ID Set
00110  * storage. If ID is valid, the route decision is a cache generated from
00111  * route_set and link_set, and it needs to be kept up-to-date with
00112  * thread_update_fast_route_table() when those change.
00113  */
00114 #define FAST_ROUTE_INVALID_ID   0xFF
00115 #define FAST_ROUTE_NO_ROUTE     0xFE
00116 #if N_THREAD_ROUTERS > 0xFD
00117 #error "rework fast_route_table"
00118 #endif
00119 
00120 typedef struct thread_routing_info_s {
00121     NS_LIST_HEAD (thread_router_link_t, link) link_set;
00122     NS_LIST_HEAD (thread_route_t, link) route_set;
00123     uint_least8_t fast_route_table[N_THREAD_ROUTERS];
00124     bool activated;
00125     bool router_id_sequence_valid;
00126     uint8_t router_id_sequence;
00127     uint16_t networkFragmentationTimer;
00128     uint16_t networkIdTimeout; //!< timeout in seconds
00129     trickle_t mle_advert_timer;
00130 }
00131 thread_routing_info_t;
00132 
00133 #ifdef HAVE_THREAD
00134 
00135 /* See ns_types.h for explanation */
00136 NS_INLINE thread_router_id_t thread_router_id_from_addr(uint16_t addr);
00137 NS_INLINE uint16_t thread_router_addr_from_id(thread_router_id_t addr);
00138 NS_INLINE uint16_t thread_router_addr_from_addr(uint16_t addr);
00139 NS_INLINE bool thread_is_router_addr(uint16_t addr);
00140 NS_INLINE bool thread_addr_is_child(uint16_t a, uint16_t b);
00141 NS_INLINE bool thread_addr_is_equal_or_child(uint16_t a, uint16_t b);
00142 
00143 #if defined NS_ALLOW_INLINING || defined THREAD_ROUTING_FN
00144 #ifndef THREAD_ROUTING_FN
00145 #define THREAD_ROUTING_FN NS_INLINE
00146 #endif
00147 THREAD_ROUTING_FN thread_router_id_t thread_router_id_from_addr(uint16_t addr)
00148 {
00149     return addr >> THREAD_ROUTER_SHIFT;
00150 }
00151 
00152 THREAD_ROUTING_FN uint16_t thread_router_addr_from_id(thread_router_id_t addr)
00153 {
00154     return (uint_fast16_t) addr << THREAD_ROUTER_SHIFT;
00155 }
00156 
00157 THREAD_ROUTING_FN uint16_t thread_router_addr_from_addr(uint16_t addr)
00158 {
00159     return (addr & THREAD_ROUTER_MASK) | THREAD_ROUTER_IDX;
00160 }
00161 
00162 THREAD_ROUTING_FN bool thread_is_router_addr(uint16_t addr)
00163 {
00164     return (addr & ~ THREAD_ROUTER_MASK) == THREAD_ROUTER_IDX;
00165 }
00166 
00167 /* Return true if b is a child of a */
00168 THREAD_ROUTING_FN bool thread_addr_is_child(uint16_t a, uint16_t b)
00169 {
00170     if (thread_is_router_addr(b)) {
00171         return false;
00172     }
00173     return thread_router_addr_from_addr(b) == a;
00174 }
00175 
00176 /* Return true if b is equal to a, or b is a child of a */
00177 THREAD_ROUTING_FN bool thread_addr_is_equal_or_child(uint16_t a, uint16_t b)
00178 {
00179     return b == a || thread_addr_is_child(a, b);
00180 }
00181 #endif /* NS_ALLOW_INLINING || defined THREAD_ROUTING_FN */
00182 #endif // HAVE_THREAD
00183 
00184 #ifdef HAVE_THREAD_ROUTER
00185 
00186 bool thread_i_am_router(const protocol_interface_info_entry_t *cur);
00187 
00188 void thread_routing_init(thread_routing_info_t *routing);
00189 void thread_routing_reset(thread_routing_info_t *routing);
00190 void thread_routing_free(thread_routing_info_t *routing);
00191 void thread_routing_activate(thread_routing_info_t *routing);
00192 void thread_routing_deactivate(thread_routing_info_t *routing);
00193 bool thread_routing_timer(struct thread_info_s *thread, uint8_t ticks);
00194 void thread_routing_trickle_advance(thread_routing_info_t *routing, uint16_t ticks);
00195 void thread_routing_leader_connection_validate(struct thread_info_s *thread, uint16_t disconnect_period);
00196 void thread_routing_set_mesh_callbacks(protocol_interface_info_entry_t *cur);
00197 
00198 uint_fast8_t thread_routing_cost_get_by_router_id(thread_routing_info_t *routing, uint8_t routerId);
00199 bool router_id_sequence_is_greater(const thread_routing_info_t *routing, uint8_t seq);
00200 
00201 uint_fast8_t thread_routing_count_neighbours_for_downgrade(thread_routing_info_t *routing, uint_fast8_t *as_good);
00202 uint_fast8_t thread_routing_count_active_routers(thread_routing_info_t *routing);
00203 uint_fast8_t thread_routing_count_active_routers_from_mask(const uint8_t *id_mask);
00204 
00205 //Init
00206 void thread_routing_update_id_set(protocol_interface_info_entry_t *cur, uint8_t seq, const uint8_t *id_mask);
00207 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);
00208 
00209 int_fast8_t thread_routing_update_link_margin(protocol_interface_info_entry_t *cur,
00210                                               uint16_t sender,
00211                                               uint8_t link_margin_db,
00212                                               uint8_t outgoing_link_margin_db);
00213 int_fast8_t thread_routing_force_link_margin(protocol_interface_info_entry_t *cur,
00214                                              uint16_t addr,
00215                                              uint8_t link_margin_db);
00216 int_fast8_t thread_routing_add_link(protocol_interface_info_entry_t *cur,
00217                                     uint16_t sender, uint8_t link_margin_db,
00218                                     uint8_t id_seq,
00219                                     const uint8_t *id_mask,
00220                                     const uint8_t *route_data,
00221                                     bool is_static);
00222 int_fast8_t thread_routing_remove_link(protocol_interface_info_entry_t *cur,
00223                                        uint16_t sender);
00224 
00225 uint8_t thread_routing_get_route_data_size(protocol_interface_info_entry_t *cur);
00226 
00227 int_fast8_t thread_routing_get_route_data(protocol_interface_info_entry_t *cur,
00228                                           uint8_t *id_seq,
00229                                           uint8_t *id_mask,
00230                                           uint8_t *data,
00231                                           uint8_t *len_out);
00232 #else // HAVE_THREAD_ROUTER
00233 
00234 #define thread_i_am_router(cur) false
00235 #define thread_routing_init(routing)
00236 #define thread_routing_reset(routing)
00237 #define thread_routing_free(routing)
00238 #define thread_routing_activate(routing)
00239 #define thread_routing_deactivate(routing)
00240 #define thread_routing_timer(thread, ticks) false
00241 #define thread_routing_trickle_advance(routing, ticks)
00242 #define thread_routing_leader_connection_validate(thread, disconnect_period)
00243 #define thread_routing_set_mesh_callbacks(cur)
00244 #define thread_routing_cost_get_by_router_id(routing, routerId) (0)
00245 #define thread_routing_count_active_routers(routing) 0
00246 #define thread_routing_count_active_routers_from_mask(id_mask) 0
00247 #define thread_routing_update_id_set(cur, seq, id_mask)
00248 #define thread_routing_update_link_margin(cur, sender, link_margin_db, outgoing_link_margin_db) (-3)
00249 #define thread_routing_force_link_margin(cur, addr, link_margin_db) (-3)
00250 #define thread_routing_add_link(cur, sender, link_margin_db, id_seq, id_mask, route_data, is_static) (-2)
00251 #define thread_is_router_addr(addr) false
00252 #define thread_routing_remove_link(cur, sender) 0
00253 #define thread_routing_get_route_data_size(cur) 0
00254 #define thread_routing_get_route_data(cur,id_seq,id_mask,data,len_out) (0)
00255 #define thread_addr_is_equal_or_child(a, b) false
00256 #define thread_addr_is_child(a, b) false
00257 
00258 #endif // HAVE_THREAD_ROUTER
00259 
00260 #endif /* THREAD_ROUTING_H_ */