public inbox for passt-dev@passt.top
 help / color / mirror / code / Atom feed
From: David Gibson <david@gibson.dropbear.id.au>
To: passt-dev@passt.top, Stefano Brivio <sbrivio@redhat.com>
Cc: Markus Armbruster <armbru@redhat.com>,
	David Gibson <david@gibson.dropbear.id.au>
Subject: [PATCH v2 2/2] util: Remove possible quadratic behaviour from write_remainder()
Date: Tue, 17 Sep 2024 16:45:55 +1000	[thread overview]
Message-ID: <20240917064555.1040365-3-david@gibson.dropbear.id.au> (raw)
In-Reply-To: <20240917064555.1040365-1-david@gibson.dropbear.id.au>

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.  With
an unfortunate set of write sizes this could lead to quadratic behaviour.

In an even less likely set of circumstances (total vector length > maximum
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 out
the remainder of its complaint).

Rework write_remainder() to always work out our new position in the vector
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 <david@gibson.dropbear.id.au>
---
 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
  */
 int write_remainder(int fd, const struct iovec *iov, size_t iovcnt, size_t skip)
 {
-	size_t offset, i;
+	size_t i = 0, offset;
 
-	while ((i = iov_skip_bytes(iov, iovcnt, skip, &offset)) < iovcnt) {
+	while ((i += iov_skip_bytes(iov + i, iovcnt - i, skip, &offset)) < iovcnt) {
 		ssize_t rc;
 
 		if (offset) {
-			rc = write(fd, (char *)iov[i].iov_base + offset,
-				   iov[i].iov_len - offset);
-		} else {
-			rc = 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++;
 		}
 
+		/* Write as much of the remaining whole buffers as we can */
+		rc = writev(fd, &iov[i], iovcnt - i);
 		if (rc < 0)
 			return -1;
 
-		skip += rc;
+		skip = rc;
 	}
-
 	return 0;
 }
 
-- 
@@ -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
  */
 int write_remainder(int fd, const struct iovec *iov, size_t iovcnt, size_t skip)
 {
-	size_t offset, i;
+	size_t i = 0, offset;
 
-	while ((i = iov_skip_bytes(iov, iovcnt, skip, &offset)) < iovcnt) {
+	while ((i += iov_skip_bytes(iov + i, iovcnt - i, skip, &offset)) < iovcnt) {
 		ssize_t rc;
 
 		if (offset) {
-			rc = write(fd, (char *)iov[i].iov_base + offset,
-				   iov[i].iov_len - offset);
-		} else {
-			rc = 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++;
 		}
 
+		/* Write as much of the remaining whole buffers as we can */
+		rc = writev(fd, &iov[i], iovcnt - i);
 		if (rc < 0)
 			return -1;
 
-		skip += rc;
+		skip = rc;
 	}
-
 	return 0;
 }
 
-- 
2.46.0


  parent reply	other threads:[~2024-09-17  6:46 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2024-09-17  6:45 [PATCH v2 0/2] util: Fix some problems in write_remainder() David Gibson
2024-09-17  6:45 ` [PATCH v2 1/2] util: Add helper to write() all of a buffer David Gibson
2024-09-18  6:05   ` Markus Armbruster
2024-09-18 10:22     ` David Gibson
2024-09-17  6:45 ` David Gibson [this message]
2024-09-18  6:20   ` [PATCH v2 2/2] util: Remove possible quadratic behaviour from write_remainder() Markus Armbruster
2024-09-18 10:27     ` David Gibson

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20240917064555.1040365-3-david@gibson.dropbear.id.au \
    --to=david@gibson.dropbear.id.au \
    --cc=armbru@redhat.com \
    --cc=passt-dev@passt.top \
    --cc=sbrivio@redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://passt.top/passt

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for IMAP folder(s).