From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from gandalf.ozlabs.org (gandalf.ozlabs.org [150.107.74.76]) by passt.top (Postfix) with ESMTPS id 4C3D65A026F for ; Mon, 1 Jan 2024 13:01:29 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202312; t=1704110483; bh=v5Z2gE70HY9uy6qOvBff8+ZESQPa80jBLzWKhq8ZvuM=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=kQwIx4tdpPMubBohJi9uELIMF0x1JAhe/5OW6In3r7atA1QVqNE0/dRNEMw2qV1TG Jis4at2E2ibgKuqNUUenpGcuP1bD8cs/GnL392N7+MQwmVz9H8eDtpSwdeBfah4iqF dp/HOFZYomFiKC8wK6K7V6tR+k0sHok6oz2OuyiMw7k8fcbly/Bi3uaw9Bz7+lTGmA 30CAM7K09gWAhJdtHrDqzj416msfr4pZY2q0rV6plMfPXxRSivaxaWSMF7KWUewTvf aMMaezeu8EMBgehAJorOp2W/nTnnfuYvwQqBfIKWZsJ8CM2+/A3rMBiADNSWN6IdZZ Me83S13ZkGKog== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4T3ZMR4Lxkz4wch; Mon, 1 Jan 2024 23:01:23 +1100 (AEDT) Date: Mon, 1 Jan 2024 23:01:17 +1100 From: David Gibson To: Stefano Brivio Subject: Re: [PATCH v3 13/13] flow: Avoid moving flow entries to compact table Message-ID: References: <20231221061549.976358-1-david@gibson.dropbear.id.au> <20231221061549.976358-14-david@gibson.dropbear.id.au> <20231228192525.7ba1ee48@elisabeth> <20231230113304.37c60a9a@elisabeth> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="RMejcDzbn/AGK7lx" Content-Disposition: inline In-Reply-To: <20231230113304.37c60a9a@elisabeth> Message-ID-Hash: BNQ224KRDWITSZIOUNCZ4W7YDKRQUJKO X-Message-ID-Hash: BNQ224KRDWITSZIOUNCZ4W7YDKRQUJKO 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: 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: --RMejcDzbn/AGK7lx Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Dec 30, 2023 at 11:33:04AM +0100, Stefano Brivio wrote: > On Thu, 28 Dec 2023 19:25:25 +0100 > Stefano Brivio wrote: >=20 > > > On Thu, 21 Dec 2023 17:15:49 +1100 > > > David Gibson wrote: > > >=20 > > > [...] > > > > [...] > > > > I wonder if we really have to keep track of the number of (non-)entries > > in the free "block", and if we have to be explicit about the two cases. > >=20 > > I'm trying to find out if we can simplify the whole thing with slightly > > different variants, for example: >=20 > So... I think the version with (explicit) blocks has this fundamental > advantage, on deletion: >=20 > > > + flow->f.type =3D FLOW_TYPE_NONE; > > > + /* Put it back in a length 1 free block, don't attempt to fully rev= erse > > > + * flow_alloc()s steps. This will get folded together the next time > > > + * flow_defer_handler runs anyway() */ > > > + flow->free.n =3D 1; > > > + flow->free.next =3D flow_first_free; > > > + flow_first_free =3D FLOW_IDX(flow); >=20 > which is doable even without explicit blocks, but much harder to > follow. Remember this is not a general deletion, only a "cancel" of the most recent allocation. To reduce fragmentation we are keeping the linked list of free clusters in strictly ascending order. The logic above is only correct if the entry we're freeing is before any other free entry in the table. That will be the case for the most recent allocation, because we always allocatte the first free entry in the table. > Other than the comments I have, I would go ahead with your approach. My > attempt below in case you're interested. The comment at the end of > flow_del() shows the issue I'm facing: >=20 > struct flow_free_block { > /* Must be first element */ > struct flow_common f; >=20 > unsigned next_free; > unsigned next_used; > }; >=20 > static union flow *flow_alloc(void) > { > union flow *flow; >=20 > if (flow_first_free >=3D FLOW_MAX) > return NULL; >=20 > flow =3D flowtab + flow_first_free; >=20 > flow_first_free =3D flow->free.next_free; >=20 > memset(flow, 0, sizeof(*flow)); /* TODO: select region */ > return flow; > } >=20 > static void flow_del(union flow *del) > { > union flow *left, *right, *next_used =3D NULL, *first_free; fg >=20 > del->f.type =3D FLOW_TYPE_NONE; >=20 > left =3D (FLOW_IDX(del) > 0) ? FLOW(FLOW_IDX(del) - 1) : NUL= L; > right =3D (FLOW_IDX(del) < FLOW_MAX - 1) ? FLOW(FLOW_IDX(del) + 1) : NUL= L; >=20 > first_free =3D flow_first_free < FLOW_MAX ? FLOW(flow_first_free) : NULL; >=20 > if (right) { > if (right->f.type =3D=3D FLOW_TYPE_NONE) > del->free.next_used =3D right->free.next_used; > else > del->free.next_used =3D right; > } else { > del->free.next_used =3D FLOW_MAX; > } >=20 > if (left && left->f.type =3D=3D FLOW_TYPE_NONE) { > left->free.next_free =3D FLOW_IDX(del); > left->free.next_used =3D del->free.next_used; > return; > } >=20 > if (flow_first_free =3D=3D FLOW_MAX) { > flow_first_free =3D FLOW_IDX(del); > } else if (flow_first_free > FLOW_IDX(del)) { > flow_first_free =3D FLOW_IDX(del); > del->free.next_free =3D flow_first_free; > } else if (flow_first_free < FLOW_IDX(del)) { > ; > /* Walk free slots from flow_first_free until FLOW_IDX(del) to > * find insertion point... but that makes deletion at most O(n), > * perhaps O(log(n)), certainly not O(1). Exactly. I can't see any way (short of far more complex data structures) around having a linear scan somewhere, although you can kind of choose whether it happens on alloc or free. The idea of my implementation is to have it at free time - but to merge it with an existing linear scan so it won't have an additional cost. > * > * Or just link out-of-order for the moment, and fix this up in > * flow_next(), but then "blocks" help representing this. > */ > } > } >=20 > static union flow *flow_next(union flow *whence) > { > if (FLOW_IDX(whence) >=3D FLOW_MAX - 1) > return NULL; >=20 > if (whence->f.type !=3D FLOW_TYPE_NONE) > whence++; >=20 > if (whence->f.type =3D=3D FLOW_TYPE_NONE) > return whence->free.next_used; >=20 > return whence; > } >=20 --=20 David Gibson | 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 --RMejcDzbn/AGK7lx Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmWSqXMACgkQzQJF27ox 2GcrRxAAlkdg+RDSDP0hZorN9pyfH3KlgPZCfzdMtZeyM9mXd+zb/Pj/gL9A9rZd wW9FW71bmD2yugcALDnqZk7NPXSWM5lCPzaHbMDUKh757bk/BWlpvnIH6s6RONb8 I7so5Kdhb2tsBoJILMlN1mD06jVCYB1V1r/gOkZrFXb9obbSIVsJ0g1+PklHn+u7 s73bZ/4lf571UF54t89ajuS+BocuGCuxCFEveXvWImkSe04lao1hV9pRj39VxwoB Tbv2A/m3bqM25xFS+j58rinpiLXLnQlcPVFjBdqDNldD0XRlSaGw4ygOyjZRI1Dq BmMTLW/IjK8UByqLv3oaPf2wOf5yHMxTlYHXR3TAJxag4CsYiqoxubyT+CzX/9de 0mMl9rDGJrQqyIHhLEafmiors2J1rv61qKhJRrRntUX4/BlUmsnMZxMyqmZ6w3cn H1Zo72Gzlz+q+9n/S1BfKLfQuy4G86DjIT7LBe5Fht5JzkIcBDmaTq1lKknW348Z 3ERvzi9Anup6jBlghJyPUiHsi76qhHsWxUH+Ezr2KQEp20N1amusmjSwwVNZxXJZ xtfVns7I/WglAvfSP0842AKHMvq/DHPZIwOB/2PRwEhRQM0/ELJePojYHcmmYmfw ag8nlz4ZcDXU5hd5v/XksIzhAyNHDjbvPPJmfbNw5MQPYcwLUY4= =JXjn -----END PGP SIGNATURE----- --RMejcDzbn/AGK7lx--