On Fri, Sep 05, 2025 at 10:11:47PM -0400, Jon Maloy wrote:
Because we are going to do ARP/NDP lookup of many non-local addresses the table might eventually fill up with placeholder entries which will never be completed. We therefore need an aging mechanism based on access frequency, so that we can evict the least used entries when a new one is created when the table is full.
Signed-off-by: Jon Maloy
--- v5: - New --- fwd.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 92 insertions(+)
diff --git a/fwd.c b/fwd.c index 236e58e..ab49dba 100644 --- a/fwd.c +++ b/fwd.c @@ -46,6 +46,8 @@ struct mac_cache_entry { unsigned char mac[ETH_ALEN]; struct timespec expiry; uint32_t count; + struct mac_cache_entry *qprev; + struct mac_cache_entry *qnext;
/* Hash bucket chain */ struct mac_cache_entry *next; @@ -55,6 +57,10 @@ struct mac_cache_table { struct mac_cache_entry **buckets; size_t nbuckets; size_t size; + + /* FIFO/LRU queue */ + struct mac_cache_entry *qhead; + struct mac_cache_entry *qtail; };
This will need reworking for an allocation-free table. I feel like there should be a simpler way to do this than a full doubly linked pointer list, but it's not immediately obvious to me.
static struct mac_cache_table mac_cache; @@ -81,6 +87,82 @@ static inline size_t fwd_mac_cache_bucket_idx(const struct ctx *c, return ((size_t)h) & (nbuckets - 1); }
+/** + * fwd_mac_cacheq_append_tail() - Unlink entry from LRU queue + * @c: Execution context + */ +static void fwd_mac_cacheq_append_tail(struct mac_cache_entry *e) +{ + struct mac_cache_table *t = &mac_cache; + + e->qnext = NULL; + e->qprev = t->qtail; + if (t->qtail) + t->qtail->qnext = e; + else + t->qhead = e; + t->qtail = e; +} + +/** + * fwd_mac_cacheq_unlink() - Unlink entry from LRU queue + * @c: Execution context + */ +static void fwd_mac_cacheq_unlink(struct mac_cache_entry *e) +{ + struct mac_cache_table *t = &mac_cache; + + if (e->qprev) + e->qprev->qnext = e->qnext; + else + t->qhead = e->qnext; + if (e->qnext) + e->qnext->qprev = e->qprev; + else + t->qtail = e->qprev; + e->qprev = e->qnext = NULL; +} + +/** + * fwd_mac_cacheq_move_to_tail() - Move entry to tail of LRU queue + * @c: Execution context + */ +static void fwd_mac_cacheq_move_to_tail(struct mac_cache_entry *e) +{ + struct mac_cache_table *t = &mac_cache; + + if (t->qtail == e) + return; + + fwd_mac_cacheq_unlink(e); + fwd_mac_cacheq_append_tail(e); +} + +/** + * fwd_mac_cache_evict_one() - Remove entry from head of LRU queue + * @c: Execution context + */ +static void fwd_mac_cache_evict_one(const struct ctx *c) +{ + struct mac_cache_entry **pp, *e, *cursor; + struct mac_cache_table *t = &mac_cache; + size_t idx; + + e = t->qhead; + if (!e) + return; + + idx = fwd_mac_cache_bucket_idx(c, &e->key, t->nbuckets); + for (pp = &t->buckets[idx]; ((cursor = *pp)); pp = &cursor->next) { + if (cursor != e) + continue; + *pp = cursor->next; + break; + } + free(e); + t->size--; +} + /** * timespec_before() - Check the relation between two pints in time * @a: Point in time to be tested @@ -179,6 +261,11 @@ static struct mac_cache_entry *fwd_mac_cache_add(const struct ctx *c, e->next = t->buckets[idx]; t->buckets[idx] = e;
+ /* If needed, delete least recently used entry before adding new one */ + if (t->size == MAC_CACHE_BUCKETS) + fwd_mac_cache_evict_one(c); + fwd_mac_cacheq_append_tail(e); + return e; }
@@ -213,6 +300,9 @@ bool fwd_neigh_mac_get(const struct ctx *c, const union inany_addr *addr, mac_entry_set_expiry(e, MAC_CACHE_RENEWAL); }
+ /* Actively used entries must not be evicted from cache */ + fwd_mac_cacheq_move_to_tail(e); + if (ret) { memcpy(mac, e->mac, ETH_ALEN); return true; @@ -235,7 +325,9 @@ int fwd_mac_cache_init(void)
t->nbuckets = MAC_CACHE_BUCKETS; t->buckets = calloc(t->nbuckets, sizeof(*t->buckets)); + t->qhead = t->qtail = NULL; t->size = 0; + return t->buckets ? 0 : -1; }
-- 2.50.1
-- David Gibson (he or they) | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you, not the other way | around. http://www.ozlabs.org/~dgibson