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

[Jon Maloy <jmaloy@redhat.com>]

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;
 };
 
 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;
 }
 
-- 
@@ -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;
 };
 
 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