Re: [PATCH v5 03/10] fwd: Add entries of ARP/NDP cache table to a FIFO/LRU queue

[David Gibson <david@gibson.dropbear.id.au>]

[-- Attachment #1: Type: text/plain, Size: 4709 bytes --]

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 <jmaloy@redhat.com>
> 
> ---
> 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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]