ipv6_routing_table.c

00001 /*
00002  * Copyright (c) 2012-2018, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License");
00006  * you may not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  *     http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 /*
00018  * ipv6_routing_table.c
00019  *
00020  *  Implements IPv6 Neighbour Cache (RFC 4861), Destination Cache (RFC 4861),
00021  *  and Routing Table (RFC 4191, incorporating the RFC 4861 Prefix List)
00022  *
00023  * Note that RFC 4861 dictates that the Prefix List is checked first,
00024  * followed by the Default Router List. In simple host scenarios, the
00025  * longest-match routing table look-up achieves that, because on-link entries
00026  * from the Prefix List are longer than the ::/0 default routes.
00027  *
00028  * In more complex scenarios, we can have more-specific routes preferred over
00029  * more general on-link prefixes, eg the border router preferring a /128 RPL
00030  * DAO-SR route instead of the /64 on-link prefix for the Ethernet backbone.
00031  *
00032  */
00033 #include "nsconfig.h"
00034 #include "ns_types.h"
00035 #include "common_functions.h"
00036 #include "ip6string.h"
00037 #include "randLIB.h"
00038 #include "ns_trace.h"
00039 #include "string.h"
00040 #include "Core/include/address.h"
00041 #include "ipv6_stack/ipv6_routing_table.h"
00042 #include "Common_Protocols/ipv6_constants.h"
00043 #include "Common_Protocols/icmpv6.h"
00044 #include "nsdynmemLIB.h"
00045 #include "Service_Libs/etx/etx.h"
00046 #include "Common_Protocols/ipv6_resolution.h"
00047 #include <stdarg.h>
00048 #include <stdio.h>
00049 
00050 #define TRACE_GROUP "rout"
00051 
00052 #define NCACHE_GC_PERIOD    20  /* seconds */
00053 #define DCACHE_GC_PERIOD    20  /* seconds */
00054 
00055 static uint16_t current_max_cache = 64;
00056 
00057 /* We track "lifetime" of garbage-collectible entries, resetting
00058  * when used. Entries with lifetime 0 are favoured
00059  * for garbage-collection. */
00060 #define NCACHE_GC_AGE 600   /* 10 minutes (1s units - decremented every slow timer call) */
00061 #define DCACHE_GC_AGE 30    /* 10 minutes (20s units - decremented once per periodic GC) */
00062 #define DCACHE_GC_AGE_LL 6  /* 2 minutes for link-local destinations */
00063 
00064 /* For probable routers, consider them unreachable if ETX is greater than this */
00065 #define ETX_REACHABILITY_THRESHOLD 0x200    /* 8.8 fixed-point, so 2 */
00066 
00067 static NS_LIST_DEFINE(ipv6_destination_cache, ipv6_destination_t, link);
00068 static NS_LIST_DEFINE(ipv6_routing_table, ipv6_route_t, link);
00069 
00070 static ipv6_destination_t *ipv6_destination_lookup(const uint8_t *address, int8_t interface_id);
00071 static void ipv6_destination_cache_forget_router(ipv6_neighbour_cache_t *cache, const uint8_t neighbour_addr[16]);
00072 static void ipv6_destination_cache_forget_neighbour(const ipv6_neighbour_t *neighbour);
00073 static void ipv6_destination_release(ipv6_destination_t *dest);
00074 static void ipv6_route_table_remove_router(int8_t interface_id, const uint8_t *addr, ipv6_route_src_t source);
00075 static uint16_t total_metric(const ipv6_route_t *route);
00076 static uint8_t ipv6_route_table_count_source(int8_t interface_id, ipv6_route_src_t source);
00077 static void ipv6_route_table_remove_last_one_from_source(int8_t interface_id, ipv6_route_src_t source);
00078 static uint8_t ipv6_route_table_get_max_entries(int8_t interface_id, ipv6_route_src_t source);
00079 
00080 static uint16_t dcache_gc_timer;
00081 
00082 static uint16_t cache_long_term(bool is_destination)
00083 {
00084     uint16_t value = current_max_cache/8;
00085     if (is_destination) {
00086         value*=2;
00087     }
00088     if (value < 4) {
00089         value = 4;
00090     }
00091     return value;
00092 }
00093 
00094 static uint16_t cache_short_term(bool is_destination)
00095 {
00096     uint16_t value = current_max_cache/2;
00097     if (value < cache_long_term(is_destination)) {
00098         return cache_long_term(is_destination);
00099     }
00100     return value;
00101 }
00102 
00103 static uint32_t next_probe_time(ipv6_neighbour_cache_t *cache, uint_fast8_t retrans_num)
00104 {
00105     uint32_t t = cache->retrans_timer;
00106 
00107     while (retrans_num--) {
00108         t *= BACKOFF_MULTIPLE;
00109         if (t > MAX_RETRANS_TIMER) {
00110             t = MAX_RETRANS_TIMER;
00111             break;
00112         }
00113     }
00114 
00115     return randLIB_randomise_base(t, 0x4000, 0xBFFF);
00116 }
00117 
00118 int8_t ipv6_neighbour_set_current_max_cache(uint16_t max_cache)
00119 {
00120     if (max_cache < 4) {
00121         return -1;
00122     }
00123     current_max_cache = max_cache;
00124     return 0;
00125 }
00126 
00127 /* Called when we determine a neighbour is no longer a router */
00128 void ipv6_router_gone(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *entry)
00129 {
00130     tr_debug("Router gone: %s", trace_ipv6(entry->ip_address));
00131     entry->is_router = false;
00132     /* Only delete RA routes to satisfy RFC 4861. We should have a callback to
00133      * other route providers here - eg RPL might want to know, and delete from
00134      * the Candidate Neighbour set. But unfortunately our 6LoWPAN-ND routers do
00135      * currently send RS packets while running, which means this would break
00136      * stuff. We get spurious switches of IsRouter to false :(
00137      */
00138     ipv6_route_table_remove_router(cache->interface_id, entry->ip_address, ROUTE_RADV);
00139     /* The above will re-evaluate all destinations affected by the routing
00140      * change; the below is needed to also forget redirections to the router.
00141      */
00142     ipv6_destination_cache_forget_router(cache, entry->ip_address);
00143 }
00144 
00145 /* Called when a neighbour has apparently become reachable */
00146 static void ipv6_neighbour_appeared(ipv6_neighbour_cache_t *cache, uint8_t address[static 16])
00147 {
00148     (void)cache;
00149     (void)address;
00150 }
00151 
00152 /* Called when a neighbour has apparently become unreachable */
00153 static void ipv6_neighbour_gone(ipv6_neighbour_cache_t *cache, uint8_t address[static 16])
00154 {
00155     (void) cache;
00156     tr_debug("Lost contact with neighbour: %s", trace_ipv6(address));
00157     // We can keep trying to talk directly to that neighbour, but should
00158     // avoid using it any more as a router, if there's an alternative.
00159     ipv6_destination_cache_forget_router(cache, address);
00160 }
00161 
00162 void ipv6_neighbour_cache_init(ipv6_neighbour_cache_t *cache, int8_t interface_id)
00163 {
00164     /* Init Double linked Routing Table */
00165     ns_list_foreach_safe(ipv6_neighbour_t, cur, &cache->list) {
00166         ipv6_neighbour_entry_remove(cache, cur);
00167     }
00168     cache->gc_timer = NCACHE_GC_PERIOD;
00169     cache->retrans_timer = 1000;
00170     cache->max_ll_len = 0;
00171     cache->interface_id = interface_id;
00172     cache->recv_addr_reg = false;
00173     cache->send_addr_reg = false;
00174     cache->send_nud_probes = true;
00175     cache->recv_na_aro = false;
00176     cache->recv_ns_aro = false;
00177     cache->route_if_info.metric = 0;
00178     memset(cache->route_if_info.sources, 0, sizeof(cache->route_if_info.sources));
00179 }
00180 
00181 void ipv6_neighbour_cache_flush(ipv6_neighbour_cache_t *cache)
00182 {
00183     /* Flush non-registered entries only */
00184     ns_list_foreach_safe(ipv6_neighbour_t, cur, &cache->list) {
00185         if (cur->type == IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00186             ipv6_neighbour_entry_remove(cache, cur);
00187         }
00188     }
00189 }
00190 
00191 
00192 ipv6_neighbour_t *ipv6_neighbour_lookup(ipv6_neighbour_cache_t *cache, const uint8_t *address)
00193 {
00194     ns_list_foreach(ipv6_neighbour_t, cur, &cache->list) {
00195         if (addr_ipv6_equal(cur->ip_address, address)) {
00196             return cur;
00197         }
00198     }
00199 
00200     return NULL;
00201 }
00202 
00203 ipv6_neighbour_t *ipv6_neighbour_lookup_by_interface_id(int8_t interface_id, const uint8_t *address)
00204 {
00205     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(interface_id);
00206     if (!ncache) {
00207         return NULL;
00208     }
00209 
00210     return ipv6_neighbour_lookup(ncache, address);
00211 }
00212 
00213 
00214 void ipv6_neighbour_entry_remove(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *entry)
00215 {
00216     /* Remove entry from cache first - avoids weird garbage collection issues, like
00217      * it being pushed out while generating ICMP errors, or ICMP errors actually using
00218      * the entry.
00219      */
00220     ns_list_remove(&cache->list, entry);
00221     switch (entry->state) {
00222         case IP_NEIGHBOUR_NEW:
00223             break;
00224         case IP_NEIGHBOUR_INCOMPLETE:
00225             /* If the NCE is discarded, the queued packet must also be discarded */
00226             /* Handle this here to avoid leakage in the event that the NCE is */
00227             /* dropped by garbage collection rather than the expected timeout */
00228             ipv6_interface_resolution_failed(cache, entry);
00229             break;
00230         case IP_NEIGHBOUR_STALE:
00231         case IP_NEIGHBOUR_REACHABLE:
00232         case IP_NEIGHBOUR_DELAY:
00233         case IP_NEIGHBOUR_PROBE:
00234         case IP_NEIGHBOUR_UNREACHABLE:
00235             /* Destination cache no longer has direct pointers to neighbour cache,
00236              * so a NCE being deleted no longer necessarily needs any special
00237              * action. Neighbour GC needn't affect the Dest Cache.
00238              */
00239             // ipv6_neighbour_gone(cache, entry);
00240             break;
00241     }
00242     ipv6_destination_cache_forget_neighbour(entry);
00243     ns_dyn_mem_free(entry);
00244 }
00245 
00246 ipv6_neighbour_t *ipv6_neighbour_lookup_or_create(ipv6_neighbour_cache_t *cache, const uint8_t *address/*, bool tentative*/)
00247 {
00248     uint_fast16_t count = 0;
00249     ipv6_neighbour_t *entry = NULL;
00250 
00251     ns_list_foreach(ipv6_neighbour_t, cur, &cache->list) {
00252         count++;
00253         if (addr_ipv6_equal(cur->ip_address, address)) {
00254             if (cur != ns_list_get_first(&cache->list)) {
00255                 ns_list_remove(&cache->list, cur);
00256                 ns_list_add_to_start(&cache->list, cur);
00257             }
00258             return cur;
00259         }
00260     }
00261 
00262     if (count >= current_max_cache) {
00263         entry = ns_list_get_last(&cache->list);
00264         ipv6_neighbour_entry_remove(cache, entry);
00265     }
00266 
00267     // Allocate new - note we have a basic size, plus enough for the LL address,
00268     // plus another 8 for the EUI-64 of registration (RFC 6775). Note that in
00269     // the protocols, the link-layer address and EUI-64 are distinct. The
00270     // neighbour may be using a short link-layer address, not its EUI-64.
00271     entry = ns_dyn_mem_alloc(sizeof(ipv6_neighbour_t) + cache->max_ll_len + (cache->recv_addr_reg ? 8 : 0));
00272     if (!entry) {
00273         tr_warn("No mem!");
00274         return NULL;
00275     }
00276 
00277     memcpy(entry->ip_address, address, 16);
00278     entry->is_router = false;
00279     entry->from_redirect = false;
00280     entry->state = IP_NEIGHBOUR_NEW;
00281     /*if (tentative && cache->reg_required)
00282         entry->type = IP_NEIGHBOUR_TENTATIVE;
00283     else*/
00284     entry->type = IP_NEIGHBOUR_GARBAGE_COLLECTIBLE;
00285     ns_list_init(&entry->queue);
00286     entry->timer = 0;
00287     entry->lifetime = 0;
00288     entry->retrans_count = 0;
00289     entry->ll_type = ADDR_NONE ;
00290     if (cache->recv_addr_reg) {
00291         memset(ipv6_neighbour_eui64(cache, entry), 0, 8);
00292     }
00293 
00294     ns_list_add_to_start(&cache->list, entry);
00295 
00296     return entry;
00297 }
00298 
00299 ipv6_neighbour_t *ipv6_neighbour_lookup_or_create_by_interface_id(int8_t interface_id, const uint8_t *address/*, bool tentative*/)
00300 {
00301     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(interface_id);
00302     if (!ncache) {
00303         return NULL;
00304     }
00305 
00306     return ipv6_neighbour_lookup_or_create(ncache, address/*, tentative*/);
00307 }
00308 
00309 ipv6_neighbour_t *ipv6_neighbour_used(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *entry)
00310 {
00311     /* Reset the GC life, if it's a GC entry */
00312     if (entry->type == IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00313         entry->lifetime = NCACHE_GC_AGE;
00314     }
00315 
00316     /* Move it to the front of the list */
00317     if (entry != ns_list_get_first(&cache->list)) {
00318         ns_list_remove(&cache->list, entry);
00319         ns_list_add_to_start(&cache->list, entry);
00320     }
00321 
00322     /* If the entry is stale, prepare delay timer for active NUD probe */
00323     if (entry->state == IP_NEIGHBOUR_STALE && cache->send_nud_probes) {
00324         ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_DELAY);
00325     }
00326 
00327     /* Special case for Registered Unreachable entries - restart the probe timer if stopped */
00328     else if (entry->state == IP_NEIGHBOUR_UNREACHABLE && entry->timer == 0) {
00329         entry->timer = next_probe_time(cache, entry->retrans_count);
00330     }
00331 
00332     return entry;
00333 }
00334 
00335 static bool ipv6_neighbour_state_is_probably_reachable(ip_neighbour_cache_state_t state)
00336 {
00337     switch (state) {
00338         case IP_NEIGHBOUR_NEW:
00339         case IP_NEIGHBOUR_INCOMPLETE:
00340         case IP_NEIGHBOUR_UNREACHABLE:
00341             return false;
00342         case IP_NEIGHBOUR_REACHABLE:
00343         case IP_NEIGHBOUR_STALE:
00344         case IP_NEIGHBOUR_DELAY:
00345         case IP_NEIGHBOUR_PROBE:
00346             return true;
00347     }
00348     return false;
00349 }
00350 
00351 bool ipv6_neighbour_is_probably_reachable(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *n)
00352 {
00353     if (!n) {
00354         return false;
00355     }
00356     if (!ipv6_neighbour_state_is_probably_reachable(n->state)) {
00357         return false;
00358     }
00359     uint16_t etx = ipv6_map_ip_to_ll_and_call_ll_addr_handler(NULL, cache->interface_id, n, n->ip_address, etx_read);
00360     if (etx > ETX_REACHABILITY_THRESHOLD) {
00361         /* "Unknown" is signalled as low values, so will be return "true" */
00362         return false;
00363     }
00364     return true;
00365 }
00366 
00367 bool ipv6_neighbour_addr_is_probably_reachable(ipv6_neighbour_cache_t *cache, const uint8_t *address)
00368 {
00369     return ipv6_neighbour_is_probably_reachable(cache, ipv6_neighbour_lookup(cache, address));
00370 }
00371 
00372 bool ipv6_neighbour_ll_addr_match(const ipv6_neighbour_t *entry, addrtype_t ll_type, const uint8_t *ll_address)
00373 {
00374     return ll_type == entry->ll_type && memcmp(entry->ll_address, ll_address, addr_len_from_type(ll_type)) == 0;
00375 }
00376 
00377 static bool ipv6_neighbour_update_ll(ipv6_neighbour_t *entry, addrtype_t ll_type, const uint8_t *ll_address)
00378 {
00379     uint8_t ll_len = addr_len_from_type(ll_type);
00380 
00381     /* Any new address info clears the "redirected" flag - redirect itself
00382      * sets it again after this is called.
00383      */
00384     entry->from_redirect = false;
00385 
00386     if (ll_type != entry->ll_type || memcmp(entry->ll_address, ll_address, ll_len)) {
00387         entry->ll_type = ll_type;
00388         memcpy(entry->ll_address, ll_address, ll_len);
00389         return true;
00390     }
00391     return false;
00392 }
00393 
00394 void ipv6_neighbour_invalidate_ll_addr(ipv6_neighbour_cache_t *cache, addrtype_t ll_type, const uint8_t *ll_address)
00395 {
00396     ns_list_foreach_safe(ipv6_neighbour_t, cur, &cache->list) {
00397         if (cur->type == IP_NEIGHBOUR_GARBAGE_COLLECTIBLE && ipv6_neighbour_ll_addr_match(cur, ll_type, ll_address)) {
00398             ipv6_neighbour_entry_remove(cache, cur);
00399         }
00400     }
00401 }
00402 
00403 void ipv6_neighbour_delete_registered_by_eui64(ipv6_neighbour_cache_t *cache, const uint8_t *eui64)
00404 {
00405     ns_list_foreach_safe(ipv6_neighbour_t, cur, &cache->list) {
00406         if (cur->type != IP_NEIGHBOUR_GARBAGE_COLLECTIBLE && memcmp(ipv6_neighbour_eui64(cache, cur), eui64, 8) == 0) {
00407             ipv6_neighbour_entry_remove(cache, cur);
00408         }
00409     }
00410 }
00411 
00412 void ipv6_neighbour_set_state(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *entry, ip_neighbour_cache_state_t state)
00413 {
00414     if (!ipv6_neighbour_state_is_probably_reachable(entry->state) &&
00415             ipv6_neighbour_state_is_probably_reachable(state)) {
00416         /* A neighbour is becoming reachable - may affect destination cache */
00417         ipv6_neighbour_appeared(cache, entry->ip_address);
00418     }
00419     switch (state) {
00420         case IP_NEIGHBOUR_INCOMPLETE:
00421             entry->retrans_count = 0;
00422             entry->timer = cache->retrans_timer;
00423             break;
00424         case IP_NEIGHBOUR_STALE:
00425             entry->timer = 0;
00426             break;
00427         case IP_NEIGHBOUR_DELAY:
00428             entry->timer = DELAY_FIRST_PROBE_TIME;
00429             break;
00430         case IP_NEIGHBOUR_PROBE:
00431             entry->retrans_count = 0;
00432             entry->timer = next_probe_time(cache, 0);
00433             break;
00434         case IP_NEIGHBOUR_REACHABLE:
00435             entry->timer = cache->reachable_time;
00436             break;
00437         case IP_NEIGHBOUR_UNREACHABLE:
00438             /* Progress to this from PROBE - timers continue */
00439             ipv6_neighbour_gone(cache, entry->ip_address);
00440             break;
00441         default:
00442             entry->timer = 0;
00443             break;
00444     }
00445     entry->state = state;
00446 }
00447 
00448 /* Called when LL address information is received other than in an NA (NS source, RS source, RA source, Redirect target) */
00449 void ipv6_neighbour_entry_update_unsolicited(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *entry, addrtype_t type, const uint8_t *ll_address/*, bool tentative*/)
00450 {
00451     bool modified_ll = ipv6_neighbour_update_ll(entry, type, ll_address);
00452 
00453     switch (entry->state) {
00454         case IP_NEIGHBOUR_NEW:
00455             ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_STALE);
00456             break;
00457         case IP_NEIGHBOUR_INCOMPLETE:
00458             ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_STALE);
00459             ipv6_send_queued(entry);
00460             break;
00461         default:
00462             if (modified_ll) {
00463                 ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_STALE);
00464             }
00465             break;
00466     }
00467 }
00468 
00469 ipv6_neighbour_t *ipv6_neighbour_update_unsolicited(ipv6_neighbour_cache_t *cache, const uint8_t *ip_address, addrtype_t type, const uint8_t *ll_address/*, bool tentative*/)
00470 {
00471     ipv6_neighbour_t *entry = ipv6_neighbour_lookup_or_create(cache, ip_address/*, tentative*/);
00472     if (!entry) {
00473         return NULL;
00474     }
00475 
00476     ipv6_neighbour_entry_update_unsolicited(cache, entry, type, ll_address/*, tentative*/);
00477 
00478     return entry;
00479 }
00480 
00481 void ipv6_neighbour_update_from_na(ipv6_neighbour_cache_t *cache, ipv6_neighbour_t *entry, uint8_t flags, addrtype_t ll_type, const uint8_t *ll_address)
00482 {
00483     if (entry->state == IP_NEIGHBOUR_NEW || entry->state == IP_NEIGHBOUR_INCOMPLETE) {
00484         entry->is_router = flags & NA_R;
00485         if (ll_type == ADDR_NONE ) {
00486             return;
00487         }
00488 
00489         ipv6_neighbour_update_ll(entry, ll_type, ll_address);
00490         if (flags & NA_S) {
00491             ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_REACHABLE);
00492         } else {
00493             ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_STALE);
00494         }
00495         ipv6_send_queued(entry);
00496         return;
00497     }
00498 
00499     /* Already have a complete entry with known LL address */
00500     bool ll_addr_differs = ll_type != ADDR_NONE  && !ipv6_neighbour_ll_addr_match(entry, ll_type, ll_address);
00501 
00502     if (ll_addr_differs) {
00503         if (flags & NA_O) {
00504             entry->ll_type = ll_type;
00505             memcpy(entry->ll_address, ll_address, addr_len_from_type(ll_type));
00506         } else {
00507             if (entry->state == IP_NEIGHBOUR_REACHABLE) {
00508                 ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_STALE);
00509             }
00510             return;
00511         }
00512     }
00513 
00514     if (flags & NA_S) {
00515         ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_REACHABLE);
00516     } else if (ll_addr_differs) {
00517         ipv6_neighbour_set_state(cache, entry, IP_NEIGHBOUR_STALE);
00518     }
00519 
00520     if (entry->is_router && !(flags & NA_R)) {
00521         ipv6_router_gone(cache, entry);
00522     }
00523 
00524     entry->is_router = flags & NA_R;
00525 }
00526 
00527 void ipv6_neighbour_reachability_confirmation(const uint8_t ip_address[static 16], int8_t interface_id)
00528 {
00529     /* No point creating an entry if doesn't exist */
00530     ipv6_destination_t *dest = ipv6_destination_lookup(ip_address, interface_id);
00531     if (!dest) {
00532         return;
00533     }
00534 
00535     /* We can't be absolutely certain which next hop is working, but last_neighbour is our best guess */
00536     ipv6_neighbour_t *next_hop = dest->last_neighbour;
00537 #if 0
00538     if (next_hop) {
00539         tr_debug("%s rconf: mark %s reachable", trace_ipv6(ip_address), trace_ipv6(next_hop->ip_address));
00540     } else {
00541         tr_debug("%s rconf: next hop unknown", trace_ipv6(ip_address));
00542     }
00543 #endif
00544     if (!next_hop) {
00545         return;
00546     }
00547 
00548     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(dest->interface_id);
00549     if (!ncache) {
00550         return;
00551     }
00552 
00553     if (next_hop->state != IP_NEIGHBOUR_NEW && next_hop->state != IP_NEIGHBOUR_INCOMPLETE) {
00554         ipv6_neighbour_set_state(ncache, next_hop, IP_NEIGHBOUR_REACHABLE);
00555     }
00556 }
00557 
00558 /* RFC 4861 doesn't have this, but would seem sensible to at least nudge it out of REACHABLE state.
00559  * This doesn't add a new state machine transition, we just cut short the timer.
00560  * This should normally be called /before/ initiating a retransmit, so the
00561  * retransmit then triggers an immediate transition into DELAY state.
00562  */
00563 void ipv6_neighbour_reachability_problem(const uint8_t ip_address[static 16], int8_t interface_id)
00564 {
00565     /* No point creating an entry if doesn't exist */
00566     ipv6_destination_t *dest = ipv6_destination_lookup(ip_address, interface_id);
00567     if (!dest) {
00568         return;
00569     }
00570 
00571     /* We can't be absolutely certain which next hop has problems, but last_neighbour is our best guess */
00572     ipv6_neighbour_t *next_hop = dest->last_neighbour;
00573     if (!next_hop) {
00574         return;
00575     }
00576 
00577     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(dest->interface_id);
00578     if (!ncache) {
00579         return;
00580     }
00581 
00582     if (next_hop->state == IP_NEIGHBOUR_REACHABLE) {
00583         ipv6_neighbour_set_state(ncache, next_hop, IP_NEIGHBOUR_STALE);
00584     }
00585 }
00586 
00587 static const char *state_names[] = {
00588     [IP_NEIGHBOUR_NEW]          = "NEW",
00589     [IP_NEIGHBOUR_INCOMPLETE]   = "INCOMPLETE",
00590     [IP_NEIGHBOUR_STALE]        = "STALE",
00591     [IP_NEIGHBOUR_REACHABLE]    = "REACHABLE",
00592     [IP_NEIGHBOUR_DELAY]        = "DELAY",
00593     [IP_NEIGHBOUR_PROBE]        = "PROBE",
00594     [IP_NEIGHBOUR_UNREACHABLE]  = "UNREACHABLE",
00595 };
00596 
00597 static const char *type_names[] = {
00598     [IP_NEIGHBOUR_GARBAGE_COLLECTIBLE]  = "GC",
00599     [IP_NEIGHBOUR_REGISTERED]           = "REGISTERED",
00600     [IP_NEIGHBOUR_TENTATIVE]            = "TENTATIVE",
00601 };
00602 
00603 static void sprint_array(char *s, const uint8_t *ptr, uint_fast8_t len)
00604 {
00605     if (len == 0) {
00606         *s = '\0';
00607         return;
00608     }
00609 
00610     for (uint_fast8_t i = 0; i < len; i++) {
00611         s += sprintf(s, "%02x:", *ptr++);
00612     }
00613     // Replace last ':' with '\0'
00614     *(s - 1) = '\0';
00615 }
00616 
00617 void ipv6_neighbour_cache_print(const ipv6_neighbour_cache_t *cache, route_print_fn_t *print_fn)
00618 {
00619     print_fn("Neighbour Cache %d", cache->interface_id);
00620     print_fn("Reachable Time: %"PRIu32"   Retrans Timer: %"PRIu32"   MTU: %"PRIu16"", cache->reachable_time, cache->retrans_timer, cache->link_mtu);
00621     ns_list_foreach(const ipv6_neighbour_t, cur, &cache->list) {
00622         ROUTE_PRINT_ADDR_STR_BUFFER_INIT(addr_str);
00623         print_fn("%sIP Addr: %s", cur->is_router ? "Router " : "", ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, cur->ip_address));
00624         // Reusing addr_str for the array prints as it's no longer needed and 41 bytes is more than enough.
00625         sprint_array(addr_str, cur->ll_address, addr_len_from_type(cur->ll_type));
00626         print_fn("LL Addr: (%s %"PRIu32") %s", state_names[cur->state], cur->timer, addr_str);
00627         if (cache->recv_addr_reg && memcmp(ipv6_neighbour_eui64(cache, cur), ADDR_EUI64_ZERO, 8)) {
00628             sprint_array( addr_str, ipv6_neighbour_eui64(cache, cur), 8);
00629             print_fn("EUI-64:  (%s %"PRIu32") %s", type_names[cur->type], cur->lifetime, addr_str);
00630         } else if (cur->type != IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00631             print_fn("         (%s %"PRIu32") [no EUI-64]", type_names[cur->type], cur->lifetime);
00632         }
00633     }
00634 }
00635 
00636 static void ipv6_neighbour_cache_gc_periodic(ipv6_neighbour_cache_t *cache)
00637 {
00638     uint_fast16_t gc_count = 0;
00639     ns_list_foreach_safe(ipv6_neighbour_t, entry, &cache->list) {
00640         if (entry->type == IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00641             gc_count++;
00642         }
00643     }
00644 
00645     if (gc_count <= cache_long_term(false)) {
00646         return;
00647     }
00648 
00649     /* Removal strategy - to stay below MAX_SHORT_TERM, we will chuck any STALE entries */
00650     /* To stay below MAX_LONG_TERM, we will chuck old STALE entries */
00651     ns_list_foreach_reverse_safe(ipv6_neighbour_t, entry, &cache->list) {
00652         /* Expiration of non-GC entries handled in slow timer routine */
00653         if (entry->type != IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00654             continue;
00655         }
00656 
00657         if (entry->state != IP_NEIGHBOUR_STALE && entry->state != IP_NEIGHBOUR_UNREACHABLE) {
00658             continue;
00659         }
00660 
00661         if (entry->lifetime == 0 || gc_count > cache_short_term(false)) {
00662             ipv6_neighbour_entry_remove(cache, entry);
00663             if (--gc_count <= cache_long_term(false)) {
00664                 break;
00665             }
00666         }
00667     }
00668 }
00669 
00670 void ipv6_neighbour_cache_slow_timer(ipv6_neighbour_cache_t *cache, uint8_t seconds)
00671 {
00672     ns_list_foreach_safe(ipv6_neighbour_t, cur, &cache->list) {
00673         if (cur->lifetime == 0 || cur->lifetime == 0xffffffff) {
00674             continue;
00675         }
00676 
00677         if (cur->lifetime > seconds) {
00678             cur->lifetime -= seconds;
00679             continue;
00680         }
00681 
00682         cur->lifetime = 0;
00683 
00684         /* Lifetime expired */
00685         switch (cur->type) {
00686             case IP_NEIGHBOUR_GARBAGE_COLLECTIBLE:
00687                 /* No immediate action, but 0 lifetime is an input to the GC */
00688                 break;
00689 
00690             case IP_NEIGHBOUR_TENTATIVE:
00691             case IP_NEIGHBOUR_REGISTERED:
00692                 /* These are deleted as soon as lifetime expires */
00693                 ipv6_neighbour_gone(cache, cur->ip_address);
00694                 ipv6_neighbour_entry_remove(cache, cur);
00695                 break;
00696         }
00697     }
00698 
00699     if (cache->gc_timer > seconds) {
00700         cache->gc_timer -= seconds;
00701         return;
00702     }
00703 
00704     cache->gc_timer = NCACHE_GC_PERIOD;
00705     //ipv6_neighbour_cache_print(cache);
00706     ipv6_neighbour_cache_gc_periodic(cache);
00707 }
00708 
00709 void ipv6_neighbour_cache_fast_timer(ipv6_neighbour_cache_t *cache, uint16_t ticks)
00710 {
00711     uint32_t ms = (uint32_t) ticks * 100;
00712 
00713     ns_list_foreach_safe(ipv6_neighbour_t, cur, &cache->list) {
00714         if (cur->timer == 0) {
00715             continue;
00716         }
00717 
00718         if (cur->timer > ms) {
00719             cur->timer -= ms;
00720             continue;
00721         }
00722 
00723         cur->timer = 0;
00724 
00725         /* Timer expired */
00726         switch (cur->state) {
00727             case IP_NEIGHBOUR_NEW:
00728                 /* Shouldn't happen */
00729                 break;
00730             case IP_NEIGHBOUR_INCOMPLETE:
00731                 if (++cur->retrans_count >= MAX_MULTICAST_SOLICIT) {
00732                     /* Should be safe for registration - Tentative/Registered entries can't be INCOMPLETE */
00733                     ipv6_neighbour_gone(cache, cur->ip_address);
00734                     ipv6_neighbour_entry_remove(cache, cur);
00735                 } else {
00736                     ipv6_interface_resolve_send_ns(cache, cur, false, cur->retrans_count);
00737                     cur->timer = cache->retrans_timer;
00738                 }
00739                 break;
00740             case IP_NEIGHBOUR_STALE:
00741                 /* Shouldn't happen */
00742                 break;
00743             case IP_NEIGHBOUR_REACHABLE:
00744                 ipv6_neighbour_set_state(cache, cur, IP_NEIGHBOUR_STALE);
00745                 break;
00746             case IP_NEIGHBOUR_DELAY:
00747                 ipv6_neighbour_set_state(cache, cur, IP_NEIGHBOUR_PROBE);
00748                 ipv6_interface_resolve_send_ns(cache, cur, true, 0);
00749                 break;
00750             case IP_NEIGHBOUR_PROBE:
00751                 if (cur->retrans_count >= MARK_UNREACHABLE - 1) {
00752                     if (cur->from_redirect) {
00753                         ipv6_neighbour_gone(cache, cur->ip_address);
00754                         ipv6_neighbour_entry_remove(cache, cur);
00755                         break;
00756                     } else {
00757                         ipv6_neighbour_set_state(cache, cur, IP_NEIGHBOUR_UNREACHABLE);
00758                     }
00759                 }
00760             /* fall through */
00761             case IP_NEIGHBOUR_UNREACHABLE:
00762                 if (cur->retrans_count < 0xFF) {
00763                     cur->retrans_count++;
00764                 }
00765 
00766                 if (cur->retrans_count >= MAX_UNICAST_SOLICIT && cur->type == IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00767                     ipv6_neighbour_entry_remove(cache, cur);
00768                 } else {
00769                     ipv6_interface_resolve_send_ns(cache, cur, true, cur->retrans_count);
00770                     if (cur->retrans_count >= MAX_UNICAST_SOLICIT - 1) {
00771                         /* "Final" unicast probe */
00772                         if (cur->type == IP_NEIGHBOUR_GARBAGE_COLLECTIBLE) {
00773                             /* Only wait 1 initial retrans time for response to final probe - don't want backoff in this case */
00774                             cur->timer = cache->retrans_timer;
00775                         } else {
00776                             /* We're not going to remove this. Let's stop the timer. We'll restart to probe once more if it's used */
00777                             cur->timer = 0;
00778                         }
00779                     } else {
00780                         /* Backoff for the next probe */
00781                         cur->timer = next_probe_time(cache, cur->retrans_count);
00782                     }
00783                 }
00784                 break;
00785         }
00786     }
00787 }
00788 
00789 void ipv6_destination_cache_print(route_print_fn_t *print_fn)
00790 {
00791     print_fn("Destination Cache:");
00792     ns_list_foreach(ipv6_destination_t, entry, &ipv6_destination_cache) {
00793         ROUTE_PRINT_ADDR_STR_BUFFER_INIT(addr_str);
00794         print_fn(" %s (life %u)", ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, entry->destination), entry->lifetime);
00795 #ifdef HAVE_IPV6_ND
00796         if (entry->redirected) {
00797             print_fn("     Redirect %s%%%u", ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, entry->redirect_addr), entry->interface_id);
00798         }
00799 #endif
00800 #ifndef NO_IPV6_PMTUD
00801         print_fn("     PMTU %u (life %u)", entry->pmtu, entry->pmtu_lifetime);
00802 #endif
00803     }
00804 }
00805 
00806 static ipv6_destination_t *ipv6_destination_lookup(const uint8_t *address, int8_t interface_id)
00807 {
00808     bool is_ll = addr_is_ipv6_link_local(address);
00809 
00810     if (is_ll && interface_id == -1) {
00811         return NULL;
00812     }
00813 
00814     ns_list_foreach(ipv6_destination_t, cur, &ipv6_destination_cache) {
00815         if (!addr_ipv6_equal(cur->destination, address)) {
00816             continue;
00817         }
00818         /* For LL addresses, interface ID must also be compared */
00819         if (is_ll && cur->interface_id != interface_id) {
00820             continue;
00821         }
00822 
00823         return cur;
00824     }
00825 
00826     return NULL;
00827 }
00828 
00829 /* Unlike original version, this does NOT perform routing check - it's pure destination cache look-up
00830  *
00831  * We no longer attempt to cache route lookups in the destination cache, as
00832  * assumption that routing look-ups are keyed purely by destination is no longer
00833  * true. If necessary, a caching layer could be placed into
00834  * ipv6_route_choose_next_hop.
00835  *
00836  * Interface IDs are a little tricky here. Current situation is that we
00837  * require an interface ID for <=realm-local addresses, and it's ignored for
00838  * other addresses. That prevents us having multiple Destination Cache entries
00839  * for one global address.
00840  */
00841 ipv6_destination_t *ipv6_destination_lookup_or_create(const uint8_t *address, int8_t interface_id)
00842 {
00843     uint_fast16_t count = 0;
00844     ipv6_destination_t *entry = NULL;
00845     bool interface_specific = addr_ipv6_scope(address, NULL) <= IPV6_SCOPE_REALM_LOCAL;
00846 
00847     if (interface_specific && interface_id == -1) {
00848         return NULL;
00849     }
00850 
00851     /* Find any existing entry */
00852     ns_list_foreach(ipv6_destination_t, cur, &ipv6_destination_cache) {
00853         count++;
00854         if (!addr_ipv6_equal(cur->destination, address)) {
00855             continue;
00856         }
00857         /* For LL addresses, interface ID must also be compared */
00858         if (interface_specific && cur->interface_id != interface_id) {
00859             continue;
00860         }
00861 
00862         entry = cur;
00863         break;
00864     }
00865 
00866 
00867     if (!entry) {
00868         if (count > current_max_cache) {
00869             entry = ns_list_get_last(&ipv6_destination_cache);
00870             ns_list_remove(&ipv6_destination_cache, entry);
00871             ipv6_destination_release(entry);
00872         }
00873 
00874         /* If no entry, make one */
00875         entry = ns_dyn_mem_alloc(sizeof(ipv6_destination_t));
00876         if (!entry) {
00877             return NULL;
00878         }
00879         memcpy(entry->destination, address, 16);
00880         entry->refcount = 1;
00881 #ifdef HAVE_IPV6_ND
00882         entry->redirected = false;
00883 #endif
00884         entry->last_neighbour = NULL;
00885 #ifndef NO_IPV6_PMTUD
00886         entry->pmtu = 0xffff;
00887         entry->pmtu_lifetime = 0;
00888 #endif
00889 #ifndef NO_IP_FRAGMENT_TX
00890         entry->fragment_id = randLIB_get_32bit();
00891 #endif
00892         if (interface_specific) {
00893             entry->interface_id = interface_id;
00894         } else {
00895             entry->interface_id = -1;
00896         }
00897         ns_list_add_to_start(&ipv6_destination_cache, entry);
00898     } else if (entry != ns_list_get_first(&ipv6_destination_cache)) {
00899         /* If there was an entry, and it wasn't at the start, move it */
00900         ns_list_remove(&ipv6_destination_cache, entry);
00901         ns_list_add_to_start(&ipv6_destination_cache, entry);
00902     }
00903 
00904     if (addr_ipv6_scope(address, NULL) <= IPV6_SCOPE_LINK_LOCAL) {
00905         entry->lifetime = DCACHE_GC_AGE_LL;
00906     } else {
00907         entry->lifetime = DCACHE_GC_AGE;
00908     }
00909 
00910     return entry;
00911 }
00912 
00913 
00914 /* Force re-evaluation of next hop for all entries using the specified next hop as
00915  * a router. Will keep using it for direct comms.
00916  */
00917 static void ipv6_destination_cache_forget_router(ipv6_neighbour_cache_t *ncache, const uint8_t neighbour_addr[static 16])
00918 {
00919     ipv6_neighbour_t *neighbour = ipv6_neighbour_lookup(ncache, neighbour_addr);
00920 
00921     ns_list_foreach(ipv6_destination_t, entry, &ipv6_destination_cache) {
00922         if (entry->last_neighbour && entry->interface_id == ncache->interface_id && entry->last_neighbour == neighbour) {
00923             entry->last_neighbour = NULL;
00924         }
00925 #ifdef HAVE_IPV6_ND
00926         if (entry->redirected && entry->interface_id == ncache->interface_id && addr_ipv6_equal(entry->redirect_addr, neighbour_addr)) {
00927             entry->redirected = false;
00928         }
00929 #endif
00930     }
00931 }
00932 
00933 static void ipv6_destination_cache_forget_neighbour(const ipv6_neighbour_t *neighbour)
00934 {
00935     ns_list_foreach(ipv6_destination_t, entry, &ipv6_destination_cache) {
00936         if (entry->last_neighbour == neighbour) {
00937             entry->last_neighbour = NULL;
00938         }
00939     }
00940 }
00941 
00942 #ifdef HAVE_IPV6_ND
00943 void ipv6_destination_redirect(const uint8_t *dest_addr, const uint8_t *sender_addr, const uint8_t *redirect_addr, int8_t interface_id, addrtype_t ll_type, const uint8_t *ll_address)
00944 {
00945     ipv6_destination_t *dest_entry = ipv6_destination_lookup_or_create(dest_addr, interface_id);
00946     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(interface_id);
00947     bool to_router;
00948 
00949     if (!dest_entry || !ncache) {
00950         tr_warn("Redirect failure - no dest entry/ncache");
00951         return;
00952     }
00953 
00954     if (!dest_entry->last_neighbour || dest_entry->interface_id != interface_id || !addr_ipv6_equal(dest_entry->last_neighbour->ip_address, sender_addr)) {
00955         tr_warn("Redirect not sent from current next hop");
00956         return;
00957     }
00958 
00959     if (addr_ipv6_equal(redirect_addr, dest_addr)) {
00960         /* We're being told it is on-link */
00961         to_router = false;
00962     } else if (addr_is_ipv6_link_local(redirect_addr)) {
00963         /* We're being sent to a different router */
00964         to_router = true;
00965     } else {
00966         tr_debug("Invalid redirection: %s", trace_ipv6(redirect_addr));
00967         return;
00968     }
00969 
00970     // XXX need to consider invalidating/preserving other information?
00971     // Possibly not as we should only be handling this if not a router, so no
00972     // possibility of screwing up RPL. Although the "am I a router" check isn't
00973     // in place...
00974     dest_entry->redirected = true;
00975     memcpy(dest_entry->redirect_addr, redirect_addr, 16);
00976 
00977     ipv6_neighbour_t *ncache_entry = NULL;
00978 
00979     if (ll_type != ADDR_NONE ) {
00980         ncache_entry = ipv6_neighbour_update_unsolicited(ncache, redirect_addr, ll_type, ll_address);
00981         if (ncache_entry) {
00982             ncache_entry->from_redirect = true;
00983         }
00984     }
00985 
00986     if (to_router) {
00987         if (!ncache_entry) {
00988             ncache_entry = ipv6_neighbour_lookup(ncache, redirect_addr);
00989         }
00990 
00991         if (ncache_entry) {
00992             ncache_entry->is_router = true;
00993         }
00994     }
00995 
00996     tr_debug("Redirection added");
00997     tr_debug("Iface %d destination: %s", interface_id, trace_ipv6(dest_addr));
00998     tr_debug("Old next hop: %s", trace_ipv6(sender_addr));
00999     tr_debug("New next hop: %s", trace_ipv6(redirect_addr));
01000 }
01001 #endif
01002 
01003 static void ipv6_destination_release(ipv6_destination_t *dest)
01004 {
01005     if (--dest->refcount == 0) {
01006         ns_dyn_mem_free(dest);
01007     }
01008 }
01009 
01010 static void ipv6_destination_cache_gc_periodic(void)
01011 {
01012     uint_fast16_t gc_count = 0;
01013     ns_list_foreach_safe(ipv6_destination_t, entry, &ipv6_destination_cache) {
01014         if (entry->lifetime) {
01015             entry->lifetime--;
01016         }
01017         gc_count++;
01018 #ifndef NO_IPV6_PMTUD
01019         /* Purge old PMTU values */
01020         if (entry->pmtu_lifetime) {
01021             if (entry->pmtu_lifetime <= DCACHE_GC_PERIOD) {
01022                 tr_info("Resetting PMTU for: %s", trace_ipv6(entry->destination));
01023                 entry->pmtu_lifetime = 0;
01024                 uint16_t old_mtu = entry->pmtu;
01025                 if (entry->interface_id >= 0) {
01026                     entry->pmtu = ipv6_neighbour_cache_by_interface_id(entry->interface_id)->link_mtu;
01027                 } else {
01028                     entry->pmtu = 0xffff;
01029                 }
01030                 if (entry->pmtu != old_mtu) {
01031                 //   socket_pmtu_changed(entry->destination, entry->interface_id, old_mtu, entry->pmtu);
01032                 }
01033             } else {
01034                 entry->pmtu_lifetime -= DCACHE_GC_PERIOD;
01035             }
01036         }
01037 #endif
01038     }
01039 
01040     if (gc_count <= cache_long_term(true)) {
01041         return;
01042     }
01043 
01044     /* Cache is in most-recently-used-first order. GC strategy is to start from
01045      * the back, and reduce the size to "MAX_SHORT_TERM" every GC period,
01046      * deleting any entry. Timed-out entries will be deleted to keep it to
01047      * MAX_LONG_TERM.
01048      */
01049     ns_list_foreach_reverse_safe(ipv6_destination_t, entry, &ipv6_destination_cache) {
01050         if (entry->lifetime == 0 || gc_count > cache_short_term(true)) {
01051             ns_list_remove(&ipv6_destination_cache, entry);
01052             ipv6_destination_release(entry);
01053             if (--gc_count <= cache_long_term(true)) {
01054                 break;
01055             }
01056         }
01057     }
01058 
01059 }
01060 
01061 void ipv6_destination_cache_timer(uint8_t seconds)
01062 {
01063     dcache_gc_timer += seconds;
01064 
01065     if (dcache_gc_timer >= DCACHE_GC_PERIOD) {
01066         dcache_gc_timer -= DCACHE_GC_PERIOD;
01067         ipv6_destination_cache_gc_periodic();
01068         //ipv6_destination_cache_print(trace_debug_print);
01069         //ipv6_route_table_print(trace_debug_print);
01070     }
01071 }
01072 
01073 static const char *route_src_names[] = {
01074     [ROUTE_ANY]     = "?",
01075     [ROUTE_STATIC]  = "Static",
01076     [ROUTE_USER]    = "User",
01077     [ROUTE_LOOPBACK] = "Loopback",
01078     [ROUTE_RADV]    = "RAdv",
01079     [ROUTE_ARO]     = "ARO",
01080     [ROUTE_RPL_DAO] = "RPL DAO",
01081     [ROUTE_RPL_DAO_SR] = "RPL DAO SR",
01082     [ROUTE_RPL_SRH] = "RPL SRH",
01083     [ROUTE_RPL_DIO] = "RPL DIO",
01084     [ROUTE_RPL_ROOT] = "RPL Root",
01085     [ROUTE_RPL_INSTANCE] = "RPL Instance",
01086     [ROUTE_RPL_FWD_ERROR] = "RPL Fwd-Error",
01087     [ROUTE_MULTICAST] = "Multicast",
01088     [ROUTE_MPL]     = "MPL",
01089     [ROUTE_RIP]     = "RIP",
01090     [ROUTE_THREAD]  = "Thread",
01091     [ROUTE_THREAD_BORDER_ROUTER] = "Thread Network data",
01092     [ROUTE_THREAD_PROXIED_HOST] = "Thread Proxy",
01093     [ROUTE_THREAD_BBR] = "Thread BBR",
01094     [ROUTE_THREAD_PROXIED_DUA_HOST] = "Thread DUA Proxy",
01095     [ROUTE_REDIRECT] = "Redirect",
01096 };
01097 
01098 /* Which types of routes get probed as per RFC 4191 */
01099 /* (Others are assumed to be always reachable) */
01100 static const bool ipv6_route_probing[ROUTE_MAX] = {
01101     [ROUTE_RADV] = true,
01102     [ROUTE_RPL_DAO] = true,
01103     [ROUTE_RPL_DIO] = true,
01104     [ROUTE_RPL_ROOT] = true,
01105     [ROUTE_RPL_INSTANCE] = true,
01106 };
01107 
01108 /* Which route types get minimum link MTU by default */
01109 /* Makes life easier for tunnel-based systems like RPL */
01110 static const bool ipv6_route_min_mtu[ROUTE_MAX] = {
01111     [ROUTE_RPL_DAO] = true,
01112     [ROUTE_RPL_DAO_SR] = true,
01113     [ROUTE_RPL_DIO] = true,
01114     [ROUTE_RPL_ROOT] = true,
01115     [ROUTE_RPL_INSTANCE] = true,
01116     [ROUTE_MPL] = true,
01117 };
01118 
01119 // Remember when a route source has deleted an entry - allows buffers still in
01120 // event queue to have their route info invalidated.
01121 static bool ipv6_route_source_invalidated[ROUTE_MAX];
01122 
01123 static ipv6_route_predicate_fn_t *ipv6_route_predicate[ROUTE_MAX];
01124 static ipv6_route_next_hop_fn_t *ipv6_route_next_hop_computation[ROUTE_MAX];
01125 
01126 void ipv6_route_table_set_predicate_fn(ipv6_route_src_t src, ipv6_route_predicate_fn_t fn)
01127 {
01128     ipv6_route_predicate[src] = fn;
01129 }
01130 
01131 void ipv6_route_table_set_next_hop_fn(ipv6_route_src_t src, ipv6_route_next_hop_fn_t fn)
01132 {
01133     ipv6_route_next_hop_computation[src] = fn;
01134 }
01135 
01136 static void ipv6_route_print(const ipv6_route_t *route, route_print_fn_t *print_fn)
01137 {
01138     // Route prefix is variable-length, so need to zero pad for ip6tos
01139     uint8_t addr[16] = { 0 };
01140     bitcopy(addr, route->prefix, route->prefix_len);
01141     ROUTE_PRINT_ADDR_STR_BUFFER_INIT(addr_str);
01142     if (route->lifetime != 0xFFFFFFFF) {
01143         print_fn(" %24s/%-3u if:%u src:'%s' id:%d lifetime:%"PRIu32,
01144                ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, addr), route->prefix_len, route->info.interface_id,
01145                route_src_names[route->info.source], route->info.source_id, route->lifetime
01146               );
01147     } else {
01148         print_fn(" %24s/%-3u if:%u src:'%s' id:%d lifetime:infinite",
01149                ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, addr), route->prefix_len, route->info.interface_id,
01150                route_src_names[route->info.source], route->info.source_id
01151               );
01152     }
01153     if (route->on_link) {
01154         print_fn("     On-link (met %d)", total_metric(route));
01155     } else {
01156         print_fn("     next-hop %s (met %d)", ROUTE_PRINT_ADDR_STR_FORMAT(addr_str, route->info.next_hop_addr), total_metric(route));
01157     }
01158 }
01159 
01160 void ipv6_route_table_print(route_print_fn_t *print_fn)
01161 {
01162     print_fn("Routing table:");
01163     ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01164         ipv6_route_print(r, print_fn);
01165     }
01166 }
01167 
01168 /*
01169  * This function returns total effective metric, which is a combination
01170  * of 1) route metric, and 2) interface metric. Can be extended to include
01171  * protocol metric as well in the future.
01172  */
01173 static uint16_t total_metric(const ipv6_route_t *route)
01174 {
01175     ipv6_neighbour_cache_t *cache;
01176     uint16_t metric;
01177 
01178     metric = route->metric;
01179     cache = ipv6_neighbour_cache_by_interface_id(route->info.interface_id);
01180 
01181     if (cache) {
01182         metric += cache->route_if_info.metric;
01183     }
01184 
01185     return metric;
01186 }
01187 
01188 #ifdef FEA_TRACE_SUPPORT
01189 void trace_debug_print(const char *fmt, ...)
01190 {
01191     va_list ap;
01192     va_start(ap, fmt);
01193     vtracef(TRACE_LEVEL_DEBUG, TRACE_GROUP, fmt, ap);
01194     va_end(ap);
01195 }
01196 #endif
01197 
01198 static void ipv6_route_entry_remove(ipv6_route_t *route)
01199 {
01200     tr_debug("Deleted route:");
01201 #ifdef FEA_TRACE_SUPPORT
01202     ipv6_route_print(route, trace_debug_print);
01203 #endif
01204     if (route->info_autofree) {
01205         ns_dyn_mem_free(route->info.info);
01206     }
01207     if (protocol_core_buffers_in_event_queue > 0) {
01208         // Alert any buffers in the queue already routed by this source
01209         ipv6_route_source_invalidated[route->info.source] = true;
01210     }
01211     ns_list_remove(&ipv6_routing_table, route);
01212     ns_dyn_mem_free(route);
01213 }
01214 
01215 static bool ipv6_route_same_router(const ipv6_route_t *a, const ipv6_route_t *b)
01216 {
01217     if (a == b) {
01218         return true;
01219     }
01220     return !a->on_link && !b->on_link &&
01221            a->info.interface_id == b->info.interface_id &&
01222            addr_ipv6_equal(a->info.next_hop_addr, b->info.next_hop_addr);
01223 }
01224 
01225 static void ipv6_route_probe(ipv6_route_t *route)
01226 {
01227     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(route->info.interface_id);
01228     if (!ncache || !ncache->send_nud_probes || route->probe_timer) {
01229         return;
01230     }
01231 
01232     ipv6_neighbour_t *n = ipv6_neighbour_lookup_or_create(ncache, route->info.next_hop_addr);
01233     if (!n) {
01234         return;
01235     }
01236     ipv6_interface_resolve_send_ns(ncache, n, true, 0);
01237 
01238     /* We need to limit to once per minute *per router* - so set the hold-off
01239      * timer for *all* routing entries to this router
01240      */
01241     ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01242         if (ipv6_route_same_router(r, route)) {
01243             r->probe_timer = 60;
01244             r->probe = false;
01245         }
01246     }
01247 }
01248 
01249 /* Return true is a is better than b */
01250 static bool ipv6_route_is_better(const ipv6_route_t *a, const ipv6_route_t *b)
01251 {
01252     /* Prefer longer prefix */
01253     if (a->prefix_len < b->prefix_len) {
01254         return false;
01255     }
01256 
01257     if (a->prefix_len > b->prefix_len) {
01258         return true;
01259     }
01260 
01261     /* Prefer on-link */
01262     if (b->on_link && !a->on_link) {
01263         return false;
01264     }
01265 
01266     if (a->on_link && !b->on_link) {
01267         return true;
01268     }
01269 
01270     /* If prefixes exactly equal, tiebreak by metric */
01271     return total_metric(a) < total_metric(b);
01272 }
01273 
01274 /* Find the "best" route regardless of reachability, but respecting the skip flag and predicates */
01275 static ipv6_route_t *ipv6_route_find_best(const uint8_t *addr, int8_t interface_id, ipv6_route_predicate_fn_t *predicate)
01276 {
01277     ipv6_route_t *best = NULL;
01278     ns_list_foreach(ipv6_route_t, route, &ipv6_routing_table) {
01279         /* We mustn't be skipping this route */
01280         if (route->search_skip) {
01281             continue;
01282         }
01283 
01284         /* Interface must match, if caller specified */
01285         if (interface_id != -1 && interface_id != route->info.interface_id) {
01286             continue;
01287         }
01288 
01289         /* Prefix must match */
01290         if (!bitsequal(addr, route->prefix, route->prefix_len)) {
01291             continue;
01292         }
01293 
01294         /* Check the predicate for the route itself. This allows,
01295          * RPL "root" routes (the instance defaults) to be ignored in normal
01296          * lookup. Note that for caching to work properly, we require
01297          * the route predicate to produce "constant" results.
01298          */
01299         bool valid = true;
01300         if (ipv6_route_predicate[route->info.source]) {
01301             valid = ipv6_route_predicate[route->info.source](&route->info, valid);
01302         }
01303 
01304         /* Then the supplied search-specific predicate can override */
01305         if (predicate) {
01306             valid = predicate(&route->info, valid);
01307         }
01308 
01309         /* If blocked by either predicate, skip */
01310         if (!valid) {
01311             continue;
01312         }
01313 
01314         if (!best || ipv6_route_is_better(route, best)) {
01315             best = route;
01316         }
01317     }
01318     return best;
01319 }
01320 
01321 ipv6_route_t *ipv6_route_choose_next_hop(const uint8_t *dest, int8_t interface_id, ipv6_route_predicate_fn_t *predicate)
01322 {
01323     ipv6_route_t *best = NULL;
01324     bool reachable = false;
01325     bool need_to_probe = false;
01326 
01327     ns_list_foreach(ipv6_route_t, route, &ipv6_routing_table) {
01328         route->search_skip = false;
01329     }
01330 
01331     /* Search algorithm from RFC 4191, S3.2:
01332      *
01333      * When a type C host does next-hop determination and consults its
01334      * Routing Table for an off-link destination, it searches its routing
01335      * table to find the route with the longest prefix that matches the
01336      * destination, using route preference values as a tie-breaker if
01337      * multiple matching routes have the same prefix length.  If the best
01338      * route points to a non-reachable router, this router is remembered for
01339      * the algorithm described in Section 3.5 below, and the next best route
01340      * is consulted.  This check is repeated until a matching route is found
01341      * that points to a reachable router, or no matching routes remain.
01342      *
01343      * Note that rather than having a separate on-link Prefix List, we have
01344      * on-link entries. These take precedence over default routes (by their
01345      * non-0 length), but not necessarily over more-specific routes. Therefore
01346      * it is possible that we consider a few non-reachable routers first, then
01347      * fall back to on-link. This behaviour may or may not be desired, depending
01348      * on the scenario. If not desired, the router entries should have their
01349      * "probing" flag set to false, so they always take precedence over
01350      * the on-link entry.
01351      *
01352      * There is currently no mechanism for an on-link entry to always take
01353      * precedence over a more-specific route, which is what would happen if
01354      * we really did have a separate Prefix List and Routing Table. One
01355      * possibility would be a special precedence flag.
01356      */
01357     for (;;) {
01358         ipv6_route_t *route = ipv6_route_find_best(dest, interface_id, predicate);
01359         if (!route) {
01360             break;
01361         }
01362 
01363         if (route->on_link) {
01364             reachable = true;
01365         } else {
01366             /* Some routes (eg RPL SR) compute next hop on demand */
01367             if (ipv6_route_next_hop_computation[route->info.source]) {
01368                 if (!ipv6_route_next_hop_computation[route->info.source](dest, &route->info)) {
01369                     route->search_skip = true;
01370                     continue;
01371                 }
01372             }
01373 
01374             ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(route->info.interface_id);
01375             if (!ncache) {
01376                 tr_warn("Invalid interface ID in routing table!");
01377                 route->search_skip = true;
01378                 continue;
01379             }
01380 
01381             if (ncache->send_nud_probes && ipv6_route_probing[route->info.source]) {
01382                 /* Going via a router - check reachability, as per RFC 4191.
01383                  * This only applies for certain routes (currently those from RAs) */
01384                 reachable = ipv6_neighbour_addr_is_probably_reachable(ncache, route->info.next_hop_addr);
01385             } else {
01386                 /* Can't probe, so have to assume router is reachable */
01387                 reachable = true;
01388             }
01389         }
01390 
01391         if (reachable) {
01392             /* If router is reachable, we'll take it now */
01393             best = route;
01394             break;
01395         } else {
01396             /* Otherwise, note it, and look for other less-good reachable ones */
01397             route->search_skip = true;
01398 
01399             /* As we would have used it, probe to check for reachability */
01400             route->probe = need_to_probe = true;
01401 
01402             if (!best) {
01403                 best = route;
01404             }
01405             continue;
01406         }
01407     }
01408 
01409     /* This is a bit icky - data structures are routes, but we need to probe
01410      * routers - a many->1 mapping. Probe flag is set on all routes we skipped;
01411      * but we don't want to probe the router we actually chose.
01412      */
01413     if (need_to_probe) {
01414         ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01415             if (!r->probe) {
01416                 continue;
01417             }
01418             r->probe = false;
01419 
01420             /* Note that best must be set if need_to_probe is */
01421             if (!ipv6_route_same_router(r, best) && ipv6_route_is_better(r, best)) {
01422                 ipv6_route_probe(r);
01423             }
01424         }
01425     }
01426 
01427     if (best && !reachable) {
01428         /* We've chosen a non-reachable router; this means no routers were
01429          * reachable. Move it to the bottom of the list, so that next time
01430          * we do this, we try (and hence probe) another non-reachable router,
01431          * otherwise we'll never make progress. This satisfies the
01432          * round-robin requirement in RFC 4861 6.3.6.2, enhanced for RFC 4191.
01433          */
01434         ns_list_remove(&ipv6_routing_table, best);
01435         ns_list_add_to_end(&ipv6_routing_table, best);
01436     }
01437 
01438     return best;
01439 }
01440 
01441 ipv6_route_t *ipv6_route_lookup_with_info(const uint8_t *prefix, uint8_t prefix_len, int8_t interface_id, const uint8_t *next_hop, ipv6_route_src_t source, void *info, int_fast16_t src_id)
01442 {
01443     ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01444         if (interface_id == r->info.interface_id && prefix_len == r->prefix_len && bitsequal(prefix, r->prefix, prefix_len)) {
01445             if (source != ROUTE_ANY) {
01446                 if (source != r->info.source) {
01447                     continue;
01448                 }
01449                 if (info && info != r->info.info) {
01450                     continue;
01451                 }
01452                 if (src_id != -1 && src_id != r->info.source_id) {
01453                     continue;
01454                 }
01455                 if (info && ipv6_route_next_hop_computation[source]) {
01456                     /* No need to match the actual next hop - we assume info distinguishes */
01457                     return r;
01458                 }
01459             }
01460 
01461             /* "next_hop" being NULL means on-link; this is a flag in the route entry, and r->next_hop can't be NULL */
01462             if ((next_hop && r->on_link) || (!next_hop && !r->on_link)) {
01463                 continue;
01464             }
01465 
01466             if (next_hop && !r->on_link && !addr_ipv6_equal(next_hop, r->info.next_hop_addr)) {
01467                 continue;
01468             }
01469 
01470             return r;
01471         }
01472     }
01473 
01474     return NULL;
01475 }
01476 
01477 #define PREF_TO_METRIC(pref) (128 - 64 * (pref))
01478 
01479 uint8_t ipv6_route_pref_to_metric(int_fast8_t pref)
01480 {
01481     if (pref <-1 || pref > +1) {
01482         pref = 0;
01483     }
01484     return PREF_TO_METRIC(pref);
01485 }
01486 
01487 ipv6_route_t *ipv6_route_add(const uint8_t *prefix, uint8_t prefix_len, int8_t interface_id, const uint8_t *next_hop, ipv6_route_src_t source, uint32_t lifetime, int_fast8_t pref)
01488 {
01489     return ipv6_route_add_with_info(prefix, prefix_len, interface_id, next_hop, source, NULL, 0, lifetime, pref);
01490 }
01491 
01492 ipv6_route_t *ipv6_route_add_with_info(const uint8_t *prefix, uint8_t prefix_len, int8_t interface_id, const uint8_t *next_hop, ipv6_route_src_t source, void *info, uint8_t source_id, uint32_t lifetime, int_fast8_t pref)
01493 {
01494     /* Only support -1, 0 and +1 prefs, as per RFC 4191 */
01495     if (pref < -1 || pref > +1) {
01496         return NULL;
01497     }
01498 
01499     return ipv6_route_add_metric(prefix, prefix_len, interface_id, next_hop, source, info,  source_id, lifetime, PREF_TO_METRIC(pref));
01500 }
01501 
01502 ipv6_route_t *ipv6_route_add_metric(const uint8_t *prefix, uint8_t prefix_len, int8_t interface_id, const uint8_t *next_hop, ipv6_route_src_t source, void *info, uint8_t source_id, uint32_t lifetime, uint8_t metric)
01503 {
01504     ipv6_route_t *route = NULL;
01505     enum { UNCHANGED, UPDATED, NEW } changed_info = UNCHANGED;
01506 
01507     // Maybe don't need this after all? We'll just assume that the next_hop is on-link
01508     // Thread certainly wants to use ULAs...
01509 #if 0
01510     if (next_hop) {
01511         /* Currently we require that all routes must be to link-local addresses. */
01512         /* This simplifies all sorts of things - particularly that we can assume link-local addresses to be on-link. */
01513         /* It is needed to make Redirects and probes work too. */
01514         if (!addr_is_ipv6_link_local(next_hop)) {
01515             return NULL;
01516         }
01517     }
01518 #endif
01519 
01520 
01521     /* Check for matching info, in which case it's an update */
01522     route = ipv6_route_lookup_with_info(prefix, prefix_len, interface_id, next_hop, source, info, source_id);
01523 
01524     /* 0 lifetime is a deletion request (common to all protocols) */
01525     if (lifetime == 0) {
01526         if (route) {
01527             tr_debug("Zero route lifetime");
01528             ipv6_route_entry_remove(route);
01529         }
01530         return NULL;
01531     }
01532 
01533     uint8_t max_entries = ipv6_route_table_get_max_entries(interface_id, source);
01534     if (max_entries > 0) {
01535         uint8_t entries = ipv6_route_table_count_source(interface_id, source);
01536         if (entries > max_entries) {
01537             ipv6_route_table_remove_last_one_from_source(interface_id, source);
01538         }
01539     }
01540 
01541     if (!route) { /* new route */
01542         uint_fast8_t prefix_bytes = (prefix_len + 7u) / 8u;
01543         route = ns_dyn_mem_alloc(sizeof(ipv6_route_t) + prefix_bytes);
01544         if (!route) {
01545             return NULL;
01546         }
01547         memset(route->prefix, 0, prefix_bytes);
01548         bitcopy(route->prefix, prefix, prefix_len);
01549         route->prefix_len = prefix_len;
01550         route->search_skip = false;
01551         route->probe = false;
01552         route->probe_timer = 0;
01553         route->lifetime = lifetime;
01554         route->metric = metric;
01555         route->info.source = source;
01556         route->info_autofree = false;
01557         route->info.info = info;
01558         route->info.source_id = source_id;
01559         route->info.interface_id = interface_id;
01560         route->info.pmtu = ipv6_route_min_mtu[source] ? IPV6_MIN_LINK_MTU : 0xFFFF;
01561         if (next_hop) {
01562             route->on_link = false;
01563             memcpy(route->info.next_hop_addr, next_hop, 16);
01564         } else {
01565             route->on_link = true;
01566             memset(route->info.next_hop_addr, 0, 16);
01567         }
01568 
01569         /* See ipv6_route_probe - all routing entries to the same router
01570          * want to share the same hold-off time, so search and copy.
01571          */
01572         if (next_hop) {
01573             ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01574                 if (ipv6_route_same_router(r, route)) {
01575                     route->probe_timer = r->probe_timer;
01576                     break;
01577                 }
01578             }
01579         }
01580 
01581         /* Routing table will be resorted during use, thanks to probing. */
01582         /* Doesn't matter much where they start off, but put them at the */
01583         /* beginning so new routes tend to get tried first. */
01584         ns_list_add_to_start(&ipv6_routing_table, route);
01585         changed_info = NEW;
01586     } else { /* updating a route - only lifetime and metric can be changing */
01587         route->lifetime = lifetime;
01588         if (metric != route->metric) {
01589             route->metric = metric;
01590             changed_info = UPDATED;
01591         }
01592     }
01593 
01594     if (changed_info != UNCHANGED) {
01595         tr_debug("%s route:", changed_info == NEW ? "Added" : "Updated");
01596 #ifdef FEA_TRACE_SUPPORT
01597         ipv6_route_print(route, trace_debug_print);
01598 #endif
01599     }
01600 
01601     return route;
01602 }
01603 
01604 int_fast8_t ipv6_route_delete(const uint8_t *prefix, uint8_t prefix_len, int8_t interface_id, const uint8_t *next_hop, ipv6_route_src_t source)
01605 {
01606     return ipv6_route_delete_with_info(prefix, prefix_len, interface_id, next_hop, source, NULL, 0);
01607 }
01608 
01609 int_fast8_t ipv6_route_delete_with_info(const uint8_t *prefix, uint8_t prefix_len, int8_t interface_id, const uint8_t *next_hop, ipv6_route_src_t source, void *info, int_fast16_t source_id)
01610 {
01611     ipv6_route_t *route = ipv6_route_lookup_with_info(prefix, prefix_len, interface_id, next_hop, source, info, source_id);
01612     if (!route) {
01613         return -1;
01614     }
01615 
01616     ipv6_route_entry_remove(route);
01617     return 0;
01618 }
01619 
01620 void ipv6_route_table_remove_interface(int8_t interface_id)
01621 {
01622     ns_list_foreach_safe(ipv6_route_t, r, &ipv6_routing_table) {
01623         if (interface_id == r->info.interface_id) {
01624             ipv6_route_entry_remove(r);
01625         }
01626     }
01627 }
01628 
01629 static void ipv6_route_table_remove_router(int8_t interface_id, const uint8_t *addr, ipv6_route_src_t source)
01630 {
01631     ns_list_foreach_safe(ipv6_route_t, r, &ipv6_routing_table) {
01632         if (interface_id == r->info.interface_id && r->info.source == source && !r->on_link && addr_ipv6_equal(addr, r->info.next_hop_addr)) {
01633             ipv6_route_entry_remove(r);
01634         }
01635     }
01636 }
01637 
01638 /* Somewhat specialised - allow on-the-fly modification of metrics. Masking
01639  * allows for top "preference" bits to be preserved.
01640  */
01641 void ipv6_route_table_modify_router_metric(int8_t interface_id, const uint8_t *addr, ipv6_route_src_t source, uint8_t keep, uint8_t toggle)
01642 {
01643     ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01644         if (interface_id == r->info.interface_id && r->info.source == source && !r->on_link && addr_ipv6_equal(addr, r->info.next_hop_addr)) {
01645             r->metric = (r->metric & keep) ^ toggle;
01646         }
01647     }
01648 
01649 }
01650 
01651 void ipv6_route_table_remove_info(int8_t interface_id, ipv6_route_src_t source, void *info)
01652 {
01653     ns_list_foreach_safe(ipv6_route_t, r, &ipv6_routing_table) {
01654         if ((interface_id == -1 || interface_id == r->info.interface_id) && r->info.source == source && (info == NULL || r->info.info == info)) {
01655             ipv6_route_entry_remove(r);
01656         }
01657     }
01658 }
01659 
01660 static uint8_t ipv6_route_table_count_source(int8_t interface_id, ipv6_route_src_t source)
01661 {
01662     uint8_t count = 0;
01663     ns_list_foreach(ipv6_route_t, r, &ipv6_routing_table) {
01664         if (interface_id == r->info.interface_id && r->info.source == source) {
01665             count++;
01666             if (count == 0xff) {
01667                 break;
01668             }
01669         }
01670     }
01671     return count;
01672 }
01673 
01674 static void ipv6_route_table_remove_last_one_from_source(int8_t interface_id, ipv6_route_src_t source)
01675 {
01676     // Removes last i.e. oldest entry */
01677     ns_list_foreach_reverse(ipv6_route_t, r, &ipv6_routing_table) {
01678         if (interface_id == r->info.interface_id && r->info.source == source) {
01679             ipv6_route_entry_remove(r);
01680             break;
01681         }
01682     }
01683 }
01684 
01685 
01686 void ipv6_route_table_ttl_update(uint16_t seconds)
01687 {
01688     ns_list_foreach_safe(ipv6_route_t, r, &ipv6_routing_table) {
01689         if (r->probe_timer) {
01690             if (r->probe_timer > seconds) {
01691                 r->probe_timer -= seconds;
01692             } else {
01693                 r->probe_timer = 0;
01694             }
01695         }
01696 
01697         if (r->lifetime == 0xFFFFFFFF) {
01698             continue;
01699         }
01700 
01701         if (r->lifetime > seconds) {
01702             r->lifetime -= seconds;
01703             continue;
01704         }
01705 
01706         tr_debug("Route expired");
01707         ipv6_route_entry_remove(r);
01708     }
01709 }
01710 
01711 void ipv6_route_table_set_max_entries(int8_t interface_id, ipv6_route_src_t source, uint8_t max_entries)
01712 {
01713     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(interface_id);
01714 
01715     if (ncache) {
01716         ncache->route_if_info.sources[source] = max_entries;
01717     }
01718 }
01719 
01720 static uint8_t ipv6_route_table_get_max_entries(int8_t interface_id, ipv6_route_src_t source)
01721 {
01722     ipv6_neighbour_cache_t *ncache = ipv6_neighbour_cache_by_interface_id(interface_id);
01723 
01724     if (ncache) {
01725         return ncache->route_if_info.sources[source];
01726     }
01727 
01728     return 0;
01729 }
01730 
01731 bool ipv6_route_table_source_was_invalidated(ipv6_route_src_t src)
01732 {
01733     return ipv6_route_source_invalidated[src];
01734 }
01735 
01736 // Called when event queue is empty - no pending buffers so can clear invalidation flags.
01737 void ipv6_route_table_source_invalidated_reset(void)
01738 {
01739     memset(ipv6_route_source_invalidated, false, sizeof ipv6_route_source_invalidated);
01740 }