Re: [musl] realpath without procfs -- should be ready for inclusion

[Rich Felker <dalias@libc.org>]

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

On Mon, Nov 23, 2020 at 11:26:46PM -0500, Rich Felker wrote:
> On Tue, Nov 24, 2020 at 06:39:59AM +0300, Alexey Izbyshev wrote:
> > * ENOTDIR should be returned if the last component is not a
> > directory  and the path has one or more trailing slashes
> 
> Yes, that's precisely what I've been working on the past couple hours.
> I think you missed but .. will also erase a path component that's not
> a dir (e.g. /dev/null/.. -> /dev) and these are both instances of a
> common problem. I thought use of readlink covered all the ENOTDIR
> cases but it doesn't when the next component isn't covered by readlink
> or isn't present at all.
> 
> It's trivial to fix with a check after each component but that doubles
> the number of syscalls and mostly isn't necessary. I have a reworked
> draft to fix the problem by advancing over /(/|./|.$)* rather than just
> /+ after each component, so that we can lookahead and do an extra
> readlink in the cases that need it.

While this worked, it ended up being the wrong thing to do, making two
places where readlink is called, one of them with a dummy buffer. The
right way to do it is rework the flow so that the existing readlink is
"naturally" hit where needed. This amounts to:

- Letting .. processing that cancels path components go through the
  same code path as new path components, rather than handling it
  early, and just skipping the actual readlink if we already know we
  have a dir.

- Also treating a zero-length final component as something that goes
  through the readlink code path.

There was a fair amount of reorganizing needed to make this work out,
but the end result is clean and non-redundant and code size is almost
the same as before with the missing-ENOTDIR bugs.

Speaking of code size, on 32-bit archs the proposed explicit realpath
is roughly the same size as stat+fstat+fstatat (a little over 1k on
i386), which were needed to implement the old lazy realpath in terms
of procfs. So for minimal static linking, resulting code size may be
same or smaller. (Of course it's larger if stat is already linked for
other reasons.)

New draft attached. It's possible that there are regressions since I
haven't put together an automated testset. I'm not sure if I'll try to
merge it in this release cycle still or not; that probably depends on
how easy or difficult automating these tests ends up being.

Rich

[-- Attachment #2: realpath17.c --]
[-- Type: text/plain, Size: 3614 bytes --]

#define _GNU_SOURCE
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
#include <unistd.h>
#include <string.h>

static size_t slash_len(const char *s)
{
	const char *s0 = s;
	while (*s == '/') s++;
	return s-s0;
}

char *realpath(const char *restrict filename, char *restrict resolved)
{
	char stack[PATH_MAX+1];
	char output[PATH_MAX];
	size_t p, q, l, l0, cnt=0, nup=0;
	int check_dir=0;

	if (!filename) {
		errno = EINVAL;
		return 0;
	}
	l = strnlen(filename, sizeof stack);
	if (!l) {
		errno = ENOENT;
		return 0;
	}
	if (l >= PATH_MAX) goto toolong;
	p = sizeof stack - l - 1;
	q = 0;
	memcpy(stack+p, filename, l+1);

	/* Main loop. Each iteration pops the next part from stack of
	 * remaining path components and consumes any slashes that follow.
	 * If not a link, it's moved to output; if a link, contents are
	 * pushed to the stack. */
restart:
	for (; ; p+=slash_len(stack+p)) {
		/* If stack starts with /, the whole component is / or //
		 * and the output state must be reset. */
		if (stack[p] == '/') {
			check_dir=0;
			nup=0;
			q=0;
			output[q++] = '/';
			p++;
			/* Initial // is special. */
			if (stack[p] == '/' && stack[p+1] != '/')
				output[q++] = '/';
			continue;
		}

		char *z = __strchrnul(stack+p, '/');
		l0 = l = z-(stack+p);

		if (!l && !check_dir) break;

		/* Skip any . component but preserve check_dir status. */
		if (l==1 && stack[p]=='.') {
			p += l;
			continue;
		}

		/* Copy next component onto output at least temporarily, to
		 * call readlink, but wait to advance output position until
		 * determining it's not a link. */
		if (q && output[q-1] != '/') {
			if (!p) goto toolong;
			stack[--p] = '/';
			l++;
		}
		if (q+l >= PATH_MAX) goto toolong;
		memcpy(output+q, stack+p, l);
		output[q+l] = 0;
		p += l;

		int up = 0;
		if (l0==2 && stack[p-2]=='.' && stack[p-1]=='.') {
			up = 1;
			/* Any non-.. path components we could cancel start
			 * after nup repetitions of the 3-byte string "../";
			 * if there are none, accumulate .. components to
			 * later apply to cwd, if needed. */
			if (q <= 3*nup) {
				nup++;
				q += l;
				continue;
			}
			/* When previous components are already known to be
			 * directories, processing .. can skip readlink. */
			if (!check_dir) goto skip_readlink;
		}
		ssize_t k = readlink(output, stack, p);
		if (k==p) goto toolong;
		if (!k) {
			errno = ENOENT;
			return 0;
		}
		if (k<0) {
			if (errno != EINVAL) return 0;
skip_readlink:
			check_dir = 0;
			if (up) {
				while(q && output[q-1]!='/') q--;
				if (q>1 && (q>2 || output[0]!='/')) q--;
				continue;
			}
			if (l0) q += l;
			check_dir = stack[p];
			continue;
		}
		if (++cnt == SYMLOOP_MAX) {
			errno = ELOOP;
			return 0;
		}

		/* If link contents end in /, strip any slashes already on
		 * stack to avoid /->// or //->/// or spurious toolong. */
		if (stack[k-1]=='/') while (stack[p]=='/') p++;
		p -= k;
		memmove(stack+p, stack, k);

		/* Skip the stack advancement in case we have a new
		 * absolute base path. */
		goto restart;
	}

 	output[q] = 0;

	if (output[0] != '/') {
		if (!getcwd(stack, sizeof stack)) return 0;
		l = strlen(stack);
		/* Cancel any initial .. components. */
		p = 0;
		while (nup--) {
			while(l>1 && stack[l-1]!='/') l--;
			if (l>1) l--;
			p += 2;
			if (p<q) p++;
		}
		if (q-p && stack[l-1]!='/') stack[l++] = '/';
		if (l + (q-p) + 1 >= PATH_MAX) goto toolong;
		memmove(output + l, output + p, q - p + 1);
		memcpy(output, stack, l);
		q = l + q-p;
	}

	if (resolved) return memcpy(resolved, output, q+1);
	else return strdup(output);

toolong:
	errno = ENAMETOOLONG;
	return 0;
}