ipv6_routing_table.c

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