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=202408 header.b=Q/0umAyz; dkim-atps=neutral Received: from mail.ozlabs.org (gandalf.ozlabs.org [150.107.74.76]) by passt.top (Postfix) with ESMTPS id 0A5185A004E for ; Wed, 18 Sep 2024 12:39:49 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202408; t=1726655972; bh=/FKm95N/I+Xp64Wq5eMPsj5mnmOizATepD8CnvVFzP0=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Q/0umAyz2MqMUs7QilPl66wtaVcdgadcG32xgpGlHZkip2kWxoB/RP5D+Sdx15nIO Be7cxSzJYag9HYZuaUbvYSpcRQraHZI2rVylGLN88LJYVfIMGU5qT7dOCC7n8yJEv6 Nq2vWUlp9wrMSo8W8fM1hk3zoXyA/tl/yJHGS79vOyQML3cCpW7PfV8d6qFlWXSOTz A3YgL5IEnBG9bxVX+ZYu/3z/jVgfMX7KrlBriIbKiW+G6DguIQtm/r+pfbnVa0Dkh/ g462BoqF2laeczRH2zaAPffTQo5ftzKcvmPUwie7lf4oGe3F5IIelyzrLhQEQgtrJt X/W/j99g6ADvg== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4X7wBX6H69z4x6n; Wed, 18 Sep 2024 20:39:32 +1000 (AEST) Date: Wed, 18 Sep 2024 20:27:08 +1000 From: David Gibson To: Markus Armbruster Subject: Re: [PATCH v2 2/2] util: Remove possible quadratic behaviour from write_remainder() Message-ID: References: <20240917064555.1040365-1-david@gibson.dropbear.id.au> <20240917064555.1040365-3-david@gibson.dropbear.id.au> <871q1h4h5i.fsf@pond.sub.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Og8NhmOwAEeeJg+0" Content-Disposition: inline In-Reply-To: <871q1h4h5i.fsf@pond.sub.org> Message-ID-Hash: QQZS5IQL6VRM6YZWRHL25CTB5CE64FQ5 X-Message-ID-Hash: QQZS5IQL6VRM6YZWRHL25CTB5CE64FQ5 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, Stefano Brivio 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: --Og8NhmOwAEeeJg+0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Sep 18, 2024 at 08:20:25AM +0200, Markus Armbruster wrote: > David Gibson writes: >=20 > > write_remainder() steps through the buffers in an IO vector writing out > > everything past a certain byte offset. However, on each iteration it > > rescans the buffer from the beginning to find out where we're up to. W= ith > > an unfortunate set of write sizes this could lead to quadratic behaviou= r. > > > > In an even less likely set of circumstances (total vector length > maxi= mum > > size_t) the 'skip' variable could overflow. This is one factor in a > > longstanding Coverity error we've seen (although I still can't figure o= ut > > the remainder of its complaint). > > > > Rework write_remainder() to always work out our new position in the vec= tor > > relative to our old/current position, rather than starting from the > > beginning each time. As a bonus this seems to fix the Coverity error. > > > > Signed-off-by: David Gibson > > --- > > util.c | 20 +++++++++++--------- > > 1 file changed, 11 insertions(+), 9 deletions(-) > > > > diff --git a/util.c b/util.c > > index 7db7c2e7..43e5f5ec 100644 > > --- a/util.c > > +++ b/util.c > > @@ -615,28 +615,30 @@ int write_all_buf(int fd, const void *buf, size_t= len) > > * > > * Return: 0 on success, -1 on error (with errno set) > > * > > - * #syscalls write writev > > + * #syscalls writev >=20 > I'm not familiar with this annotation. I guess it's system calls used > in directly this function, not including the ones used in callees. Basically, yes. They're just slurped up by a script to generate our seccomp() filter. >=20 > > */ > > int write_remainder(int fd, const struct iovec *iov, size_t iovcnt, si= ze_t skip) > > { > > - size_t offset, i; > > + size_t i =3D 0, offset; > > =20 > > - while ((i =3D iov_skip_bytes(iov, iovcnt, skip, &offset)) < iovcnt) { > > + while ((i +=3D iov_skip_bytes(iov + i, iovcnt - i, skip, &offset)) < = iovcnt) { > > ssize_t rc; > > =20 > > if (offset) { > > - rc =3D write(fd, (char *)iov[i].iov_base + offset, > > - iov[i].iov_len - offset); > > - } else { > > - rc =3D writev(fd, &iov[i], iovcnt - i); > > + /* Write the remainder of the partially written buffer */ > > + if (write_all_buf(fd, (char *)iov[i].iov_base + offset, > > + iov[i].iov_len - offset) < 0) > > + return -1; > > + i++; > > } > > =20 > > + /* Write as much of the remaining whole buffers as we can */ > > + rc =3D writev(fd, &iov[i], iovcnt - i); >=20 > Last argument can be zero now. Okay. Yes. > > if (rc < 0) > > return -1; > > =20 > > - skip +=3D rc; > > + skip =3D rc; > > } > > - > > return 0; > > } >=20 > We could use try to save system calls by only using writev(), with > a suitably adjusted copy of @iov. But non-zero @offset should be rare, > so I guess it's not worth the bother. Actually, they're not rare - we nearly always pass a non-zero initial skip value. But write_remainder() itself is somewhat rare, and making a copy of the iov is kind of structurally awkward in passt (we don't allocate). --=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 --Og8NhmOwAEeeJg+0 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmbqqu8ACgkQzQJF27ox 2GdFyRAAniIgAxQn6bYvQovN6encFK223bsjK+rskv+Ltxx5W6C51LP1ficly/f0 KR1GY/3ri7Vsv/Xw5DtMwDifvtTQ1bNptlM1EDyK+/r7Y1V7XoN8EZKyuSSxKk0g fKUCR2Jm6X3waLvRLQrMDwFfKVJRziUl9tOWKBP173hxgMMUgYGOteeoPfsM1Rfq bRmedGoTQ8sFLwFBQrCH0q7fSR6fganmHPb9er+eXjQsQEmCPnNdE/cosqeK46EN sRM9j3ssS/cXJVM1D9Du0HRZ6QD+x9kesg6Cryj2kd3m5HURJ6Hd+1rDK6TuCE/J R3uFxX+Wnw9/JkwP4pR290oKAkxGX/4Xq2EJ38q5cjC2ZJCrHPdfmyMRC9cPEP7Z xg04BrX+aPrvn+XuzPo0s+HL3wBH7p8znBy6ob2n8m5dY6DuVgn/H8qbzHS3m0EJ TCsAWzWgXRkO3P4bTlSIJB46k0VPFycVyLfFDbJuav+t1oMD0YHzaGN+fcr2KlSW gub57nyJSdmOJH3OwAvMIaQLDyL76gWIR6bAwuCmLrHusjscuHe2ob2yui8a2sEJ jtSYZYdmA1d88+rcyaVy0ELrtr6Jo1JUQ3696E/kuGTxzrqTTKjQlciODHX93pPv TXsm1ZNavrGJdWI4kmbgovSBwJfVITtt7YmEfFsOHuHvA2ykICQ= =tUPD -----END PGP SIGNATURE----- --Og8NhmOwAEeeJg+0--