From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: passt.top; dmarc=none (p=none dis=none) header.from=gibson.dropbear.id.au Authentication-Results: passt.top; dkim=pass (2048-bit key; secure) header.d=gibson.dropbear.id.au header.i=@gibson.dropbear.id.au header.a=rsa-sha256 header.s=202508 header.b=QAvyS5I1; dkim-atps=neutral Received: from mail.ozlabs.org (mail.ozlabs.org [IPv6:2404:9400:2221:ea00::3]) by passt.top (Postfix) with ESMTPS id C8E2C5A027C for ; Mon, 08 Sep 2025 05:09:38 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202508; t=1757300974; bh=j29KYlqpn/OTy9z+xnpfcUXTbARJnbbk+aX4xeBOXEA=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=QAvyS5I1WsH0nPirLortUO2/8OGtAR1VU+ec4fmsz0C+H3QGRUqEIVPYyKhp8egYg T+03nheK5J98/dLpP73RxdIWdRTt/9IFbKboTYIuXpHQkj6WPl7VmCWgZPH49Gqvzs ulLd8B1badS2vNEC0q3f2Wb86X7KFRD+Ic5vUMYGmH59Y4syGUxaiLUdGyD6PE1Bds /KB1/HtZLy0ng5i4Ml7VfG7K1FkfAahx4U/LpgQflTT9ZHrIPep9udIrZErxKbc8+x BYP/zWYgbP5lY99zYDd5rJAOVK8WZxH4DtdB1eTRYAGecHK9FAct/75LLS+vCfK+77 qKP+xAheuVMag== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4cKsPV512cz4w9y; Mon, 8 Sep 2025 13:09:34 +1000 (AEST) Date: Mon, 8 Sep 2025 12:51:50 +1000 From: David Gibson To: Jon Maloy Subject: Re: [PATCH v5 03/10] fwd: Add entries of ARP/NDP cache table to a FIFO/LRU queue Message-ID: References: <20250906021154.2760611-1-jmaloy@redhat.com> <20250906021154.2760611-4-jmaloy@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="YYjt1Qo4ZZvq2wYC" Content-Disposition: inline In-Reply-To: <20250906021154.2760611-4-jmaloy@redhat.com> Message-ID-Hash: GLIYL53AEDGCMXO7WD3S7QZP3RGSSOQX X-Message-ID-Hash: GLIYL53AEDGCMXO7WD3S7QZP3RGSSOQX X-MailFrom: dgibson@gandalf.ozlabs.org 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 CC: sbrivio@redhat.com, dgibson@redhat.com, passt-dev@passt.top 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: --YYjt1Qo4ZZvq2wYC Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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. >=20 > Signed-off-by: Jon Maloy >=20 > --- > v5: - New > --- > fwd.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 92 insertions(+) >=20 > 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; > =20 > /* 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. > =20 > static struct mac_cache_table mac_cache; > @@ -81,6 +87,82 @@ static inline size_t fwd_mac_cache_bucket_idx(const st= ruct ctx *c, > return ((size_t)h) & (nbuckets - 1); > } > =20 > +/** > + * 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 =3D &mac_cache; > + > + e->qnext =3D NULL; > + e->qprev =3D t->qtail; > + if (t->qtail) > + t->qtail->qnext =3D e; > + else > + t->qhead =3D e; > + t->qtail =3D 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 =3D &mac_cache; > + > + if (e->qprev) > + e->qprev->qnext =3D e->qnext; > + else > + t->qhead =3D e->qnext; > + if (e->qnext) > + e->qnext->qprev =3D e->qprev; > + else > + t->qtail =3D e->qprev; > + e->qprev =3D e->qnext =3D 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 =3D &mac_cache; > + > + if (t->qtail =3D=3D 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 =3D &mac_cache; > + size_t idx; > + > + e =3D t->qhead; > + if (!e) > + return; > + > + idx =3D fwd_mac_cache_bucket_idx(c, &e->key, t->nbuckets); > + for (pp =3D &t->buckets[idx]; ((cursor =3D *pp)); pp =3D &cursor->next)= { > + if (cursor !=3D e) > + continue; > + *pp =3D 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(con= st struct ctx *c, > e->next =3D t->buckets[idx]; > t->buckets[idx] =3D e; > =20 > + /* If needed, delete least recently used entry before adding new one */ > + if (t->size =3D=3D MAC_CACHE_BUCKETS) > + fwd_mac_cache_evict_one(c); > + fwd_mac_cacheq_append_tail(e); > + > return e; > } > =20 > @@ -213,6 +300,9 @@ bool fwd_neigh_mac_get(const struct ctx *c, const uni= on inany_addr *addr, > mac_entry_set_expiry(e, MAC_CACHE_RENEWAL); > } > =20 > + /* 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) > =20 > t->nbuckets =3D MAC_CACHE_BUCKETS; > t->buckets =3D calloc(t->nbuckets, sizeof(*t->buckets)); > + t->qhead =3D t->qtail =3D NULL; > t->size =3D 0; > + > return t->buckets ? 0 : -1; > } > =20 > --=20 > 2.50.1 >=20 --=20 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 --YYjt1Qo4ZZvq2wYC Content-Type: application/pgp-signature; name=signature.asc -----BEGIN PGP SIGNATURE----- iQIzBAEBCgAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmi+RMYACgkQzQJF27ox 2Ge7yhAAiPOFa59/E0NNpyvBor+2hC2sejIm7V85lMNa1gTGYT/Jsi7/j5f7A0tS UBupLUPoBJn2VhZtKzR57z9Yu1plFkwmXIi0+OonerCRxMGbsRPZxZNQx+Pj2mEl 9l93iSTz6x56OQMWPEY+7Ec91Q0LyqwH/7wVB3+p7NgNZFSUTOMBD59jdaZkE6vG TOo6RUzEYLG7A9VV+6Hp9acQdzluoAgfTtPLreShZncDQUa25sCKhTYyFG7NWWA/ HvZX0vv+JNCWDjRyhAmdaO4aMh9MDdz35RAdfwnXey2wJfzvvwCCqBSG8EPF5M3c e+fFaasQu/1ucr8v1jLz3sqpiuaNnrfnxsP+5ssOlwhp4wzneOnWCt2ppl1yqJ2D deh4a0x+Eui5XqNvoEXjv03z6XkQc0s42nGEbjN/PjF+9Fe0F940tQPJidLaOR0R IXVZRMAddDinlTIO6ARgj3ff/q4uBAxVpRYR2KbRlbilq3mKpeUPt36GLyrYN+fc GClEc9Jo+UikIv8GsHYLVtHMQNuTSeAxl0Mt4JeULf9ggBfvYKRRrzhXw+en6p3q 9RKNwIuLiiep0wYyyWt9ZkFG7nSmpRq02azbBoPy680nOVDP2ue1MAm341bk9Jq7 Ktg+Dk+HigdWgnK5H6oO2wycktnZH3xBVwxp2l/0gwiVj4Y/4AI= =NaI5 -----END PGP SIGNATURE----- --YYjt1Qo4ZZvq2wYC--