ipv6_routing_table.c

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