mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Joakim Sindholt <opensource@zhasha.com>
To: musl@lists.openwall.com
Subject: Re: [musl] [PATCH] pack posix_spawn file actions into extraneous padding
Date: Fri, 4 Feb 2022 20:09:13 +0100	[thread overview]
Message-ID: <Yf152c5ZpA+TY4X+@wirbelwind.zhasha.com> (raw)
In-Reply-To: <YfVEgMUnilYQBbVE@wirbelwind.zhasha.com>

[-- Attachment #1: Type: text/plain, Size: 2941 bytes --]

On Sat, Jan 29, 2022 at 02:43:28PM +0100, Joakim Sindholt wrote:
> I've written this patch that packs posix_spawn file actions into the
> posix_spawn_file_actions struct padding. I'm not sure if the way I've
> split the code up is desirable. Maybe the faexpand() function needs a
> different name and to be in its own .c file; or maybe a different
> approach is preferable.

Here's a candidate v2 patch to simplify some things. Changes since the
first one:
* fa->__actions is initialized to point to itself. This makes faexpand a
  little simpler and means that ->__actions->__actions always points to
  the last file_actions struct.
* The previous version caused an increase of 32 bytes in used stack
  space in child() on amd64. This one only causes a 16 byte increase.
  I'm not sure how big of a deal-breaker that is.
* The two switches have been merged into one. This makes it simpler IMO
  but also has some consequences:

The current implementation in musl uses a pipe to communicate
success/failure back to the parent process. This means that the
file_actions struct can accidentally succeed if it tries to use the pipe
fd as a source fd or worse, overwrite the pipe fd when targeting it in
either the dup2 or open actions.
Musl solves this by moving the pipe fd if it's the target of an
operation. Currently musl will move the pipe if it's the source fd of
close or fchdir, or if it's the target fd of dup2 or open. You'll note
that the close and fchdir cases mean that instead of failing
immediately, it will dup the pipe fd, close the old pipe fd, and then do
the actual close/fchdir syscall which then fails. It's presumably
implemented this way because it's simple and doesn't really cause a
problem. The operation will result in failure regardless.

This patch, in an attempt to be very simple, introduces a similar but
perhaps slightly worse bug. The encoding of every operation is
essentially [fd, other stuff], meaning it can do the pipe move check on
the fd in the first slot. It won't work for close since the fd is
actually -fd-1, so close gets its own check. If the check is
unconditional then we might get an unnecessary move with chdir, which is
encoded as [dummy fd, -FDOP_CHDIR]. I've chosen an fd that's unlikely to
collide (INT_MAX) however if you have every fd from 0 to INT_MAX-1 open
then the pipe fd will be on fd INT_MAX and it will not be movable. The
result is that the unnecessary pipe move fails and an otherwise
perfectly legal and possible chdir action will fail.

The fix is very simple but does end up once again causing some
duplication in the op logic:
-if (fd == p) {
+if (fd == p && fa->__pad[i] != -FDOP_CHDIR) {

Alternatively you could do the whole command check twice, only move the
fd if it's the target of dup2 or open, and then have a check in fchdir
for whether it's trying to use the pipe fd as a source, like the ones
already in close and dup2.

Or maybe this bug is acceptable.

Joakim

[-- Attachment #2: 0001-pack-posix_spawn-file-actions-into-extraneous-paddin.patch --]
[-- Type: text/x-diff, Size: 11781 bytes --]

From 9f20a4d5daa19f4508bb18f28e06226b80d49b56 Mon Sep 17 00:00:00 2001
From: Joakim Sindholt <opensource@zhasha.com>
Date: Fri, 4 Feb 2022 19:42:14 +0100
Subject: [PATCH] pack posix_spawn file actions into extraneous padding

The posix_spawn_file_actions struct contains 2 int paddings of 2 and 16
ints respectively, making them ideal for packing file actions into.
The encoding used is simple: __pad0[0] contains a count and __pad
contains the actuals elements. The most important actions, dup2 and
close, are encoded as 2 and 1 int respectively.

If the first element of a sequence is negative, then it's a close and
processing stops there.
If the second element of a sequence is positive, then it's a dup2 and
processing stops there.
If the second element is negative, however, then it contains a command
and requires per-command specific processing.
In total there are 5 file actions. Their encodings are:

close: -fd-1
dup2: fd, srcfd
fchdir: fd, -FDOP_FCHDIR
chdir: INT_MAX, -FDOP_CHDIR
open: fd, -FDOP_OPEN, flags, mode

Some file actions need a string. When a string is needed it's allocated
on the tail end of a new file_actions struct. When a string is needed or
an action requires more space than is available then a new struct is
allocated and __actions is set to point to it. All the elements of the
first file_actions struct are copied to the new one. The new
file_actions struct, being the second in the list, always points to the
last file_actions struct in the list. From then on the structs all point
back in reverse order until they reach the second one again, creating a
loop. This rube-goldberg machine exists because there's nowhere to store
a last pointer for appending new actions efficiently.
As a result of this backwards allocation, the actions requiring strings
aren't stored in the same struct as the strings themselves. Rather the
string gets stored in the logically previous struct when reading.

This packing is far from optimal but it is very simple and it allows for
up to 16 close, 8 dup2, or any combination of them, without needing to
call malloc. At worst it calls malloc as much as before.
---
 src/process/fdop.h                            | 21 ++++--
 src/process/posix_spawn.c                     | 66 ++++++++++++-------
 .../posix_spawn_file_actions_addchdir.c       | 14 ++--
 .../posix_spawn_file_actions_addclose.c       | 10 +--
 .../posix_spawn_file_actions_adddup2.c        | 12 ++--
 .../posix_spawn_file_actions_addfchdir.c      | 11 ++--
 .../posix_spawn_file_actions_addopen.c        | 18 +++--
 .../posix_spawn_file_actions_destroy.c        | 11 ++--
 src/process/posix_spawn_file_actions_init.c   |  3 +-
 9 files changed, 91 insertions(+), 75 deletions(-)

diff --git a/src/process/fdop.h b/src/process/fdop.h
index 7cf733b2..65c3c9f4 100644
--- a/src/process/fdop.h
+++ b/src/process/fdop.h
@@ -4,14 +4,21 @@
 #define FDOP_CHDIR 4
 #define FDOP_FCHDIR 5
 
-struct fdop {
-	struct fdop *next, *prev;
-	int cmd, fd, srcfd, oflag;
-	mode_t mode;
-	char path[];
-};
-
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc undef
 #define free __libc_free
+
+static inline int faexpand(posix_spawn_file_actions_t *fa, size_t str)
+{
+	posix_spawn_file_actions_t *n, *blk;
+	blk = malloc(sizeof *blk + str);
+	if (!blk) return -1;
+	*blk = *fa;
+	n = fa->__actions;
+	fa->__actions = blk;
+	blk->__actions = n->__actions;
+	n->__actions = blk;
+	fa->__pad0[0] = 0;
+	return 0;
+}
diff --git a/src/process/posix_spawn.c b/src/process/posix_spawn.c
index 728551b3..c00ab0b4 100644
--- a/src/process/posix_spawn.c
+++ b/src/process/posix_spawn.c
@@ -81,33 +81,53 @@ static int child(void *args_vp)
 		    (ret=__syscall(SYS_setuid, __syscall(SYS_getuid))) )
 			goto fail;
 
-	if (fa && fa->__actions) {
-		struct fdop *op;
-		int fd;
-		for (op = fa->__actions; op->next; op = op->next);
-		for (; op; op = op->prev) {
+	if (fa) {
+		const posix_spawn_file_actions_t *first = fa;
+		const char *path;
+		int fd, srcfd, i = 0;
+
+		/* The list of actions, in reverse order, looks like this:
+		 * [0]->[1]<-[2]<-[3]
+		 *        \_______/^
+		 * so to get to the first action we to go to [0]->next->next
+		 * and to get all the way back we have to special case the
+		 * transition from [1]->[0] */
+		fa = fa->__actions;
+		fa = fa->__actions;
+		while (!(fa == first && i == fa->__pad0[0])) {
+			if (i == fa->__pad0[0]) {
+				path = (char *)(fa+1);
+				fa = fa==first->__actions ? first : fa->__actions;
+				i = 0;
+				continue;
+			}
+			fd = fa->__pad[i++];
+
 			/* It's possible that a file operation would clobber
 			 * the pipe fd used for synchronizing with the
 			 * parent. To avoid that, we dup the pipe onto
 			 * an unoccupied fd. */
-			if (op->fd == p) {
+			if (fd == p) {
 				ret = __syscall(SYS_dup, p);
 				if (ret < 0) goto fail;
 				__syscall(SYS_close, p);
 				p = ret;
 			}
-			switch(op->cmd) {
-			case FDOP_CLOSE:
-				__syscall(SYS_close, op->fd);
-				break;
-			case FDOP_DUP2:
-				fd = op->srcfd;
-				if (fd == p) {
+
+			if (fd < 0) { /* FDOP_CLOSE */
+				if (-fd-1 == p) {
+					ret = -EBADF;
+					goto fail;
+				}
+				__syscall(SYS_close, -fd-1);
+			} else switch (-(srcfd = fa->__pad[i++])) {
+			default: /* FDOP_DUP2 */
+				if (srcfd == p) {
 					ret = -EBADF;
 					goto fail;
 				}
-				if (fd != op->fd) {
-					if ((ret=__sys_dup2(fd, op->fd))<0)
+				if (srcfd != fd) {
+					if ((ret=__sys_dup2(srcfd, fd))<0)
 						goto fail;
 				} else {
 					ret = __syscall(SYS_fcntl, fd, F_GETFD);
@@ -118,20 +138,22 @@ static int child(void *args_vp)
 				}
 				break;
 			case FDOP_OPEN:
-				fd = __sys_open(op->path, op->oflag, op->mode);
-				if ((ret=fd) < 0) goto fail;
-				if (fd != op->fd) {
-					if ((ret=__sys_dup2(fd, op->fd))<0)
+				srcfd = __sys_open(path, fa->__pad[i],
+				                   fa->__pad[i+1]);
+				if ((ret=srcfd) < 0) goto fail;
+				if (srcfd != fd) {
+					if ((ret=__sys_dup2(srcfd, fd))<0)
 						goto fail;
-					__syscall(SYS_close, fd);
+					__syscall(SYS_close, srcfd);
 				}
+				i += 2;
 				break;
 			case FDOP_CHDIR:
-				ret = __syscall(SYS_chdir, op->path);
+				ret = __syscall(SYS_chdir, path);
 				if (ret<0) goto fail;
 				break;
 			case FDOP_FCHDIR:
-				ret = __syscall(SYS_fchdir, op->fd);
+				ret = __syscall(SYS_fchdir, fd);
 				if (ret<0) goto fail;
 				break;
 			}
diff --git a/src/process/posix_spawn_file_actions_addchdir.c b/src/process/posix_spawn_file_actions_addchdir.c
index 7f2590ae..01dc52bd 100644
--- a/src/process/posix_spawn_file_actions_addchdir.c
+++ b/src/process/posix_spawn_file_actions_addchdir.c
@@ -2,17 +2,15 @@
 #include <stdlib.h>
 #include <string.h>
 #include <errno.h>
+#include <limits.h>
 #include "fdop.h"
 
 int posix_spawn_file_actions_addchdir_np(posix_spawn_file_actions_t *restrict fa, const char *restrict path)
 {
-	struct fdop *op = malloc(sizeof *op + strlen(path) + 1);
-	if (!op) return ENOMEM;
-	op->cmd = FDOP_CHDIR;
-	op->fd = -1;
-	strcpy(op->path, path);
-	if ((op->next = fa->__actions)) op->next->prev = op;
-	op->prev = 0;
-	fa->__actions = op;
+	size_t len = strlen(path);
+	if (faexpand(fa, len + 1) != 0) return ENOMEM;
+	fa->__pad[fa->__pad0[0]++] = INT_MAX;
+	fa->__pad[fa->__pad0[0]++] = -FDOP_CHDIR;
+	memcpy((posix_spawn_file_actions_t *)fa->__actions + 1, path, len + 1);
 	return 0;
 }
diff --git a/src/process/posix_spawn_file_actions_addclose.c b/src/process/posix_spawn_file_actions_addclose.c
index 0c2ef8fa..c6942fc0 100644
--- a/src/process/posix_spawn_file_actions_addclose.c
+++ b/src/process/posix_spawn_file_actions_addclose.c
@@ -6,12 +6,8 @@
 int posix_spawn_file_actions_addclose(posix_spawn_file_actions_t *fa, int fd)
 {
 	if (fd < 0) return EBADF;
-	struct fdop *op = malloc(sizeof *op);
-	if (!op) return ENOMEM;
-	op->cmd = FDOP_CLOSE;
-	op->fd = fd;
-	if ((op->next = fa->__actions)) op->next->prev = op;
-	op->prev = 0;
-	fa->__actions = op;
+	if (sizeof(fa->__pad)/sizeof(*fa->__pad) - fa->__pad0[0] < 1)
+		if (faexpand(fa, 0) != 0) return ENOMEM;
+	fa->__pad[fa->__pad0[0]++] = -fd-1;
 	return 0;
 }
diff --git a/src/process/posix_spawn_file_actions_adddup2.c b/src/process/posix_spawn_file_actions_adddup2.c
index addca4d4..b2945f56 100644
--- a/src/process/posix_spawn_file_actions_adddup2.c
+++ b/src/process/posix_spawn_file_actions_adddup2.c
@@ -6,13 +6,9 @@
 int posix_spawn_file_actions_adddup2(posix_spawn_file_actions_t *fa, int srcfd, int fd)
 {
 	if (srcfd < 0 || fd < 0) return EBADF;
-	struct fdop *op = malloc(sizeof *op);
-	if (!op) return ENOMEM;
-	op->cmd = FDOP_DUP2;
-	op->srcfd = srcfd;
-	op->fd = fd;
-	if ((op->next = fa->__actions)) op->next->prev = op;
-	op->prev = 0;
-	fa->__actions = op;
+	if (sizeof(fa->__pad)/sizeof(*fa->__pad) - fa->__pad0[0] < 2)
+		if (faexpand(fa, 0) != 0) return ENOMEM;
+	fa->__pad[fa->__pad0[0]++] = fd;
+	fa->__pad[fa->__pad0[0]++] = srcfd;
 	return 0;
 }
diff --git a/src/process/posix_spawn_file_actions_addfchdir.c b/src/process/posix_spawn_file_actions_addfchdir.c
index e89ede8c..a62a35fa 100644
--- a/src/process/posix_spawn_file_actions_addfchdir.c
+++ b/src/process/posix_spawn_file_actions_addfchdir.c
@@ -7,12 +7,9 @@
 int posix_spawn_file_actions_addfchdir_np(posix_spawn_file_actions_t *fa, int fd)
 {
 	if (fd < 0) return EBADF;
-	struct fdop *op = malloc(sizeof *op);
-	if (!op) return ENOMEM;
-	op->cmd = FDOP_FCHDIR;
-	op->fd = fd;
-	if ((op->next = fa->__actions)) op->next->prev = op;
-	op->prev = 0;
-	fa->__actions = op;
+	if (sizeof(fa->__pad)/sizeof(*fa->__pad) - fa->__pad0[0] < 2)
+		if (faexpand(fa, 0) != 0) return ENOMEM;
+	fa->__pad[fa->__pad0[0]++] = fd;
+	fa->__pad[fa->__pad0[0]++] = -FDOP_FCHDIR;
 	return 0;
 }
diff --git a/src/process/posix_spawn_file_actions_addopen.c b/src/process/posix_spawn_file_actions_addopen.c
index 82bbcec9..1c419396 100644
--- a/src/process/posix_spawn_file_actions_addopen.c
+++ b/src/process/posix_spawn_file_actions_addopen.c
@@ -6,16 +6,14 @@
 
 int posix_spawn_file_actions_addopen(posix_spawn_file_actions_t *restrict fa, int fd, const char *restrict path, int flags, mode_t mode)
 {
+	size_t len;
 	if (fd < 0) return EBADF;
-	struct fdop *op = malloc(sizeof *op + strlen(path) + 1);
-	if (!op) return ENOMEM;
-	op->cmd = FDOP_OPEN;
-	op->fd = fd;
-	op->oflag = flags;
-	op->mode = mode;
-	strcpy(op->path, path);
-	if ((op->next = fa->__actions)) op->next->prev = op;
-	op->prev = 0;
-	fa->__actions = op;
+	len = strlen(path);
+	if (faexpand(fa, len + 1) != 0) return ENOMEM;
+	fa->__pad[fa->__pad0[0]++] = fd;
+	fa->__pad[fa->__pad0[0]++] = -FDOP_OPEN;
+	fa->__pad[fa->__pad0[0]++] = flags;
+	fa->__pad[fa->__pad0[0]++] = mode;
+	memcpy((posix_spawn_file_actions_t *)fa->__actions + 1, path, len + 1);
 	return 0;
 }
diff --git a/src/process/posix_spawn_file_actions_destroy.c b/src/process/posix_spawn_file_actions_destroy.c
index 3251babb..dbb9ac52 100644
--- a/src/process/posix_spawn_file_actions_destroy.c
+++ b/src/process/posix_spawn_file_actions_destroy.c
@@ -4,11 +4,12 @@
 
 int posix_spawn_file_actions_destroy(posix_spawn_file_actions_t *fa)
 {
-	struct fdop *op = fa->__actions, *next;
-	while (op) {
-		next = op->next;
-		free(op);
-		op = next;
+	posix_spawn_file_actions_t *next, *p = fa->__actions;
+	for (p = p->__actions; p != fa->__actions; p = next) {
+		next = p->__actions;
+		free(p);
 	}
+	if (p != fa)
+		free(p);
 	return 0;
 }
diff --git a/src/process/posix_spawn_file_actions_init.c b/src/process/posix_spawn_file_actions_init.c
index 89d5e127..ee9c8687 100644
--- a/src/process/posix_spawn_file_actions_init.c
+++ b/src/process/posix_spawn_file_actions_init.c
@@ -2,6 +2,7 @@
 
 int posix_spawn_file_actions_init(posix_spawn_file_actions_t *fa)
 {
-	fa->__actions = 0;
+	fa->__pad0[0] = 0;
+	fa->__actions = fa;
 	return 0;
 }
-- 
2.26.3


  reply	other threads:[~2022-02-04 19:09 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-01-29 13:43 Joakim Sindholt
2022-02-04 19:09 ` Joakim Sindholt [this message]
2022-05-04 20:10   ` Rich Felker
2022-05-06 17:07     ` Joakim Sindholt

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=Yf152c5ZpA+TY4X+@wirbelwind.zhasha.com \
    --to=opensource@zhasha.com \
    --cc=musl@lists.openwall.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://git.vuxu.org/mirror/musl/

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 NNTP newsgroup(s).