From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: passt.top; dmarc=pass (p=quarantine dis=none) header.from=redhat.com Authentication-Results: passt.top; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=ewzvcbex; dkim-atps=neutral Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by passt.top (Postfix) with ESMTPS id 8E9C55A027C for ; Sat, 06 Sep 2025 04:12:06 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1757124725; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=1U7xowLY90rY0Y4XG3xEgkSfgi5HidzuJfi+L/tZly4=; b=ewzvcbexJB1LOHRHMUrP97vYTRkW1J/zdfSJNquZUIaqz+l9PwzGJf024Ka7GUY1qDZUd7 nhF/EXv9819l7g+MBigGiUuk2fb6E3AkVXu3r3gbFgv0Tqazm5K5Otztlhi7nGvfeBZzPh OU3g/94ikxd6Wi8UftD98/sziI6xfew= Received: from mx-prod-mc-02.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-605-YRS1sQOEM6iG-6byulPExw-1; Fri, 05 Sep 2025 22:12:04 -0400 X-MC-Unique: YRS1sQOEM6iG-6byulPExw-1 X-Mimecast-MFC-AGG-ID: YRS1sQOEM6iG-6byulPExw_1757124723 Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-02.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id BBE8F195608E; Sat, 6 Sep 2025 02:12:02 +0000 (UTC) Received: from jmaloy-thinkpadp16vgen1.rmtcaqc.csb (unknown [10.22.88.21]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id AF87A18003FC; Sat, 6 Sep 2025 02:12:00 +0000 (UTC) From: Jon Maloy To: sbrivio@redhat.com, dgibson@redhat.com, david@gibson.dropbear.id.au, jmaloy@redhat.com, passt-dev@passt.top Subject: [PATCH v5 03/10] fwd: Add entries of ARP/NDP cache table to a FIFO/LRU queue Date: Fri, 5 Sep 2025 22:11:47 -0400 Message-ID: <20250906021154.2760611-4-jmaloy@redhat.com> In-Reply-To: <20250906021154.2760611-1-jmaloy@redhat.com> References: <20250906021154.2760611-1-jmaloy@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: wxXM-T58MnVkAAl8qJwBakAwH4OMm9DhItuM1ClQIKc_1757124723 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit content-type: text/plain; charset="US-ASCII"; x-default=true Message-ID-Hash: AOZGEJLBL66UKIB7B66POKDAU3O3HNUK X-Message-ID-Hash: AOZGEJLBL66UKIB7B66POKDAU3O3HNUK X-MailFrom: jmaloy@redhat.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header X-Mailman-Version: 3.3.8 Precedence: list List-Id: Development discussion and patches for passt Archived-At: Archived-At: List-Archive: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: 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; }; 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