restrictness of strtoi(3bsd) and strtol(3)

restrictness of strtoi(3bsd) and strtol(3)

[Alejandro Colomar]

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

Hi,

I've been implementing my own copy of strto[iu](3bsd), to avoid the
complexity of calling strtol(3) et al.  In the process, I've noticed
that all of these functions use restrict for their parameters.

Why do these functions use restrict?  While the second parameter is not
used for accessing nptr memory (**endptr is not accessed), it can point
to the same memory.  Here is an example of how these functions can have
pointers to the same memory in the two arguments.

	l = strtol(p, &p, 0);

The use of restrict in the prototype of the function could result in
compiler warnings, no?  Currently, I don't see any warnings, but I
suspect the compiler could complain, since the same memory is available
to the function via two different arguments (albeit with a different
number of references).

The use of restrict in the definition of the function doesn't help the
optimizer, since it already knows that the second parameter is out-only,
so even if it weren't restrict, the only way to access memory is via the
first parameter.

Thanks,
Alex

-- 
<https://www.alejandro-colomar.es/>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: restrictness of strtoi(3bsd) and strtol(3)

[Alejandro Colomar]

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

On Sat, Dec 02, 2023 at 12:50:28PM +0100, Alejandro Colomar wrote:
> Hi,
> 
> I've been implementing my own copy of strto[iu](3bsd), to avoid the
> complexity of calling strtol(3) et al.  In the process, I've noticed
> that all of these functions use restrict for their parameters.
> 
> Why do these functions use restrict?  While the second parameter is not
> used for accessing nptr memory (**endptr is not accessed), it can point
> to the same memory.  Here is an example of how these functions can have
> pointers to the same memory in the two arguments.
> 
> 	l = strtol(p, &p, 0);
> 
> The use of restrict in the prototype of the function could result in
> compiler warnings, no?  Currently, I don't see any warnings, but I
> suspect the compiler could complain, since the same memory is available
> to the function via two different arguments (albeit with a different
> number of references).
> 
> The use of restrict in the definition of the function doesn't help the
> optimizer, since it already knows that the second parameter is out-only,
> so even if it weren't restrict, the only way to access memory is via the
> first parameter.

In the case of strto[iu](3bsd), I have even more doubts.

Here's libbsd's version of it (omitting unimportant parts):

	$ grepc -tfd strtoi .
	./src/strtoi.c:intmax_t
	strtoi(const char *__restrict nptr,
	       char **__restrict endptr, int base,
	       intmax_t lo, intmax_t hi, int *rstatus)
	{
		...

		im = strtoimax(nptr, endptr, base);

		*rstatus = errno;
		errno = serrno;

		if (*rstatus == 0) {
			/* No digits were found */
			if (nptr == *endptr)
				*rstatus = ECANCELED;
			/* There are further characters after number */
			else if (**endptr != '\0')
				*rstatus = ENOTSUP;
		}

		...

		return im;
	}

Let's say the base is unsupported (e.g., -42), and endptr initially
points to nptr-1.  Imagine this call:

	i = strtoimax(p + 1, &p, -42);

ISO C doesn't specify what happens if the base is not between 0 and 36,
so the behavior is probably undefined in ISO C.

POSIX says it returns 0 and sets errno to EINVAL, but doesn't say what
happens to endptr.  I expect two possible implementations:

-  Leave endptr untouched.
-  Set *endptr = nptr.

Let's suppose it leaves endptr untouched (otherwise, it would be
impossible to portably differentiate an EINVAL due to unsupported base
from an EINVAL due to no digits in the string).

So, the test (nptr == *endptr) would be false (because p+1 != p), and
the code would jump into accessing **endptr without having derived
that pointer from nptr, which is a violation of restrict.

I made many assumptions here, where the standards are not clear, so I
may be wrong in some of them.  But it looks to me like a bug.

CCing libbsd.

Cheers,
Alex

-- 
<https://www.alejandro-colomar.es/>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: restrictness of strtoi(3bsd) and strtol(3)

[Alejandro Colomar]

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

On Sat, Dec 02, 2023 at 01:29:01PM +0100, Alejandro Colomar wrote:
> On Sat, Dec 02, 2023 at 12:50:28PM +0100, Alejandro Colomar wrote:
> > Hi,
> > 
> > I've been implementing my own copy of strto[iu](3bsd), to avoid the
> > complexity of calling strtol(3) et al.  In the process, I've noticed
> > that all of these functions use restrict for their parameters.
> > 
> > Why do these functions use restrict?  While the second parameter is not
> > used for accessing nptr memory (**endptr is not accessed), it can point
> > to the same memory.  Here is an example of how these functions can have
> > pointers to the same memory in the two arguments.
> > 
> > 	l = strtol(p, &p, 0);
> > 
> > The use of restrict in the prototype of the function could result in
> > compiler warnings, no?  Currently, I don't see any warnings, but I
> > suspect the compiler could complain, since the same memory is available
> > to the function via two different arguments (albeit with a different
> > number of references).
> > 
> > The use of restrict in the definition of the function doesn't help the
> > optimizer, since it already knows that the second parameter is out-only,
> > so even if it weren't restrict, the only way to access memory is via the
> > first parameter.
> 
> In the case of strto[iu](3bsd), I have even more doubts.
> 
> Here's libbsd's version of it (omitting unimportant parts):
> 
> 	$ grepc -tfd strtoi .
> 	./src/strtoi.c:intmax_t
> 	strtoi(const char *__restrict nptr,
> 	       char **__restrict endptr, int base,
> 	       intmax_t lo, intmax_t hi, int *rstatus)
> 	{
> 		...
> 
> 		im = strtoimax(nptr, endptr, base);
> 
> 		*rstatus = errno;
> 		errno = serrno;
> 
> 		if (*rstatus == 0) {
> 			/* No digits were found */
> 			if (nptr == *endptr)
> 				*rstatus = ECANCELED;
> 			/* There are further characters after number */
> 			else if (**endptr != '\0')
> 				*rstatus = ENOTSUP;
> 		}
> 
> 		...
> 
> 		return im;
> 	}
> 
> Let's say the base is unsupported (e.g., -42), and endptr initially
> points to nptr-1.  Imagine this call:
> 
> 	i = strtoimax(p + 1, &p, -42);
> 
> ISO C doesn't specify what happens if the base is not between 0 and 36,
> so the behavior is probably undefined in ISO C.
> 
> POSIX says it returns 0 and sets errno to EINVAL, but doesn't say what
> happens to endptr.  I expect two possible implementations:
> 
> -  Leave endptr untouched.
> -  Set *endptr = nptr.
> 
> Let's suppose it leaves endptr untouched (otherwise, it would be
> impossible to portably differentiate an EINVAL due to unsupported base
> from an EINVAL due to no digits in the string).
> 
> So, the test (nptr == *endptr) would be false (because p+1 != p), and
> the code would jump into accessing **endptr without having derived
> that pointer from nptr, which is a violation of restrict.

Oops, it's within an (errno == 0) path, so *endptr is guaranteed to be
derived from nptr here.

So no bug, but still unclear to me what's the benefit of using restrict,
and also unclear why GCC doesn't warn about it at call site.

> I made many assumptions here, where the standards are not clear, so I
> may be wrong in some of them.  But it looks to me like a bug.
> 
> CCing libbsd.
> 
> Cheers,
> Alex
> 
> -- 
> <https://www.alejandro-colomar.es/>



-- 
<https://www.alejandro-colomar.es/>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: restrictness of strtoi(3bsd) and strtol(3)

[Amol Surati]

On Sat, 2 Dec 2023 at 18:05, Alejandro Colomar via Gcc-help
<gcc-help@gcc.gnu.org> wrote:
>
> On Sat, Dec 02, 2023 at 01:29:01PM +0100, Alejandro Colomar wrote:
> > On Sat, Dec 02, 2023 at 12:50:28PM +0100, Alejandro Colomar wrote:
> > > Hi,
> > >
> > > I've been implementing my own copy of strto[iu](3bsd), to avoid the
> > > complexity of calling strtol(3) et al.  In the process, I've noticed
> > > that all of these functions use restrict for their parameters.
> > >
> > > Why do these functions use restrict?  While the second parameter is not
> > > used for accessing nptr memory (**endptr is not accessed), it can point
> > > to the same memory.  Here is an example of how these functions can have
> > > pointers to the same memory in the two arguments.
> > >
> > >     l = strtol(p, &p, 0);
> > >
> > > The use of restrict in the prototype of the function could result in
> > > compiler warnings, no?  Currently, I don't see any warnings, but I
> > > suspect the compiler could complain, since the same memory is available
> > > to the function via two different arguments (albeit with a different
> > > number of references).
> > >
> > > The use of restrict in the definition of the function doesn't help the
> > > optimizer, since it already knows that the second parameter is out-only,
> > > so even if it weren't restrict, the only way to access memory is via the
> > > first parameter.
> >
> > In the case of strto[iu](3bsd), I have even more doubts.
> >
> > Here's libbsd's version of it (omitting unimportant parts):
> >
> >       $ grepc -tfd strtoi .
> >       ./src/strtoi.c:intmax_t
> >       strtoi(const char *__restrict nptr,
> >              char **__restrict endptr, int base,
> >              intmax_t lo, intmax_t hi, int *rstatus)
> >       {
> >               ...
> >
> >               im = strtoimax(nptr, endptr, base);
> >
> >               *rstatus = errno;
> >               errno = serrno;
> >
> >               if (*rstatus == 0) {
> >                       /* No digits were found */
> >                       if (nptr == *endptr)
> >                               *rstatus = ECANCELED;
> >                       /* There are further characters after number */
> >                       else if (**endptr != '\0')
> >                               *rstatus = ENOTSUP;
> >               }
> >
> >               ...
> >
> >               return im;
> >       }
> >
> > Let's say the base is unsupported (e.g., -42), and endptr initially
> > points to nptr-1.  Imagine this call:
> >
> >       i = strtoimax(p + 1, &p, -42);
> >
> > ISO C doesn't specify what happens if the base is not between 0 and 36,
> > so the behavior is probably undefined in ISO C.
> >
> > POSIX says it returns 0 and sets errno to EINVAL, but doesn't say what
> > happens to endptr.  I expect two possible implementations:
> >
> > -  Leave endptr untouched.
> > -  Set *endptr = nptr.
> >
> > Let's suppose it leaves endptr untouched (otherwise, it would be
> > impossible to portably differentiate an EINVAL due to unsupported base
> > from an EINVAL due to no digits in the string).
> >
> > So, the test (nptr == *endptr) would be false (because p+1 != p), and
> > the code would jump into accessing **endptr without having derived
> > that pointer from nptr, which is a violation of restrict.
>
> Oops, it's within an (errno == 0) path, so *endptr is guaranteed to be
> derived from nptr here.
>
> So no bug, but still unclear to me what's the benefit of using restrict,

The section "7. Library" at [1] has some information about the 'restrict'
keyword.

I think the restrict keywords compel the programmer to keep the string
(or that portion of the string that strtol actually accesses) and the
pointer to a string in non-overlapping memory regions. Calling
strtol(p, &p, 0) should be well-defined in such cases.
-------------------
[1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n881.pdf
-Amol

> and also unclear why GCC doesn't warn about it at call site.
>
> > I made many assumptions here, where the standards are not clear, so I
> > may be wrong in some of them.  But it looks to me like a bug.
> >
> > CCing libbsd.
> >
> > Cheers,
> > Alex
> >
> > --
> > <https://www.alejandro-colomar.es/>
>
>
>
> --
> <https://www.alejandro-colomar.es/>

Re: restrictness of strtoi(3bsd) and strtol(3)

[Alejandro Colomar]

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

Hello Amol,

On Sun, Dec 03, 2023 at 04:29:07PM +0530, Amol Surati wrote:
> The section "7. Library" at [1] has some information about the 'restrict'
> keyword.
> 
> I think the restrict keywords compel the programmer to keep the string
> (or that portion of the string that strtol actually accesses) and the
> pointer to a string in non-overlapping memory regions. Calling
> strtol(p, &p, 0) should be well-defined in such cases.

That would justify the restrict on char **restrict, but it doesn't
justify the const char *restrict.

I think a more appropriate prototype would be

	long
	strtol(const char *nptr, char **restrict endptr, int base);

The above means that endptr points to memory that is not pointed to by
anything else in this call.

But any of the following is somewhere between confusing and a lie:

	long
	strtol(const char *nptr,
	       char *restrict *restrict endptr,
	       int base);

	long
	strtol(const char *restrict nptr,
	       char **restrict endptr,
	       int base);

	long
	strtol(const char *restrict nptr,
	       char *restrict *restrict endptr,
	       int base);

These 3 from above all mean the same thing: nptr, endptr, and *endptr
each point to a different memory region.  That's of course a lie,
because nptr and *endptr may alias.  The formal definition by ISO C,
which is in terms of accesses, seems to be compatible with these uses of
restrict, because as long as the function doesn't access the memory, it
doesn't matter if they overlap.  However, that definition of restrict is
useless IMO, and still doesn't justify why the compiler isn't
complaining at call site, where it can't know that strtol(3) won't
use **endptr.

Cheers,
Alex

-- 
<https://www.alejandro-colomar.es/>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: restrictness of strtoi(3bsd) and strtol(3)

[Amol Surati]

Hello Alex,

On Sun, 3 Dec 2023 at 17:05, Alejandro Colomar <alx@kernel.org> wrote:
>
> Hello Amol,
>
> On Sun, Dec 03, 2023 at 04:29:07PM +0530, Amol Surati wrote:
> > The section "7. Library" at [1] has some information about the 'restrict'
> > keyword.
> >
> > I think the restrict keywords compel the programmer to keep the string
> > (or that portion of the string that strtol actually accesses) and the
> > pointer to a string in non-overlapping memory regions. Calling
> > strtol(p, &p, 0) should be well-defined in such cases.
>
> That would justify the restrict on char **restrict, but it doesn't
> justify the const char *restrict.
> I think a more appropriate prototype would be
>
>         long
>         strtol(const char *nptr, char **restrict endptr, int base);
>
> The above means that endptr points to memory that is not pointed to by
> anything else in this call.
Referring to the points you make later, removing the restrict-qualifier from
nptr then explicitly permits *endptr and nptr to alias, as the types are now
devoid of restrict-qualifiers.

>
> But any of the following is somewhere between confusing and a lie:
>
>         long
>         strtol(const char *nptr,
>                char *restrict *restrict endptr,
>                int base);
>
>         long
>         strtol(const char *restrict nptr,
>                char **restrict endptr,
>                int base);
>
>         long
>         strtol(const char *restrict nptr,
>                char *restrict *restrict endptr,
>                int base);
>
> These 3 from above all mean the same thing: nptr, endptr, and *endptr
> each point to a different memory region.  That's of course a lie,
> because nptr and *endptr may alias.  The formal definition by ISO C,
> which is in terms of accesses, seems to be compatible with these uses of
> restrict, because as long as the function doesn't access the memory, it
> doesn't matter if they overlap.  However, that definition of restrict is
> useless IMO, and still doesn't justify why the compiler isn't
> complaining at call site, where it can't know that strtol(3) won't
> use **endptr.
I think I understand. Since strtol is an external function, the compiler, when
when compiling strtol(p, &p, 0), has enough information, in the form of the
strtol prototype and a call to it, to warn about the fact that nptr and *endptr
may alias in a way that triggers an undefined behaviour.

Based on how I understood the latest draft n3096.pdf, it is the write to a
char through *endptr (along with a read of that char through nptr) that
triggers the violation of the 'restrict' clause. The read and write need not
be in a particular order. No major compiler warns, though, as evident by
an example at https://godbolt.org/z/a4xza5xna
------
What sort of optimizations can a strtol implementation hope to achieve?
A couple of libcs discard the restrict qualifier when calling their handlers
for strtol. The situation with strtol doesn't seem to be similar to that with
memcpy-memmove.

It seems that, as long as strtol does not assign a value to **endptr, it
continues to adhere to the std.

The historical docs point towards a decision to stamp the prototype with
restrict under the assumption that (1) the string and the pointer to string
are in disjoint memory locations, and (2) the implementations would
use endptr for nothing else other than maintaining a position in the given
string.

-Amol
>
> Cheers,
> Alex
>
> --
> <https://www.alejandro-colomar.es/>

Re: restrictness of strtoi(3bsd) and strtol(3)

[Alejandro Colomar]

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

Hello Amol,

On Sun, Dec 03, 2023 at 09:08:22PM +0530, Amol Surati wrote:
[...]

> Referring to the points you make later, removing the restrict-qualifier from
> nptr then explicitly permits *endptr and nptr to alias, as the types are now
> devoid of restrict-qualifiers.

[...]

> I think I understand. Since strtol is an external function, the compiler, when
> when compiling strtol(p, &p, 0), has enough information, in the form of the
> strtol prototype and a call to it, to warn about the fact that nptr and *endptr
> may alias in a way that triggers an undefined behaviour.

Exactly.

> 
> Based on how I understood the latest draft n3096.pdf, it is the write to a
> char through *endptr (along with a read of that char through nptr) that
> triggers the violation of the 'restrict' clause. The read and write need not
> be in a particular order. No major compiler warns, though, as evident by
> an example at https://godbolt.org/z/a4xza5xna

As you say, ISO C's formal definition of restrict permits pointers to
overlapping memory, as long as only one of the pointers is dereferenced.

> ------
> What sort of optimizations can a strtol implementation hope to achieve?
> A couple of libcs discard the restrict qualifier when calling their handlers
> for strtol. The situation with strtol doesn't seem to be similar to that with
> memcpy-memmove.
> 
> It seems that, as long as strtol does not assign a value to **endptr, it
> continues to adhere to the std.

To be pedantic, even reading a value from **endptr would cause UB.

But yeah, the point is there: the standard's definition of restrict
isn't very good.

> The historical docs point towards a decision to stamp the prototype with
> restrict under the assumption that (1) the string and the pointer to string
> are in disjoint memory locations,

This justifies the restrict on endptr.

> and (2) the implementations would
> use endptr for nothing else other than maintaining a position in the given
> string.

This is quite brittle.  The restrict on ntpr should cause the compiler
to scream.  I'll report a missing warning on bugzilla.

Cheers,
Alex

-- 
<https://www.alejandro-colomar.es/>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: restrictness of strtoi(3bsd) and strtol(3)

[Alejandro Colomar]

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

On Sun, Dec 03, 2023 at 05:33:59PM +0100, Alejandro Colomar wrote:
> But yeah, the point is there: the standard's definition of restrict
> isn't very good.
> 
> > The historical docs point towards a decision to stamp the prototype with
> > restrict under the assumption that (1) the string and the pointer to string
> > are in disjoint memory locations,
> 
> This justifies the restrict on endptr.
> 
> > and (2) the implementations would
> > use endptr for nothing else other than maintaining a position in the given
> > string.
> 
> This is quite brittle.  The restrict on ntpr should cause the compiler
> to scream.  I'll report a missing warning on bugzilla.

Here's a reproducer of the bug:

	$ cat restrict.c 
	long bogus_strtol(const char *restrict s, char **restrict ep, int base);

	int
	main(void)
	{
		char buf[3] = "foo";
		char *p = buf;

		bogus_strtol(p, &p, -42);
	}

	long
	bogus_strtol(const char *restrict s, char **restrict ep, int base)
	{
		**ep = *s;
		return base;
	}
	$ cc -Wall -Wextra restrict.c -fanalyzer
	$ clang -Weverything restrict.c
	$ cc -Wall -Wextra restrict.c -fanalyzer -O3
	$ clang -Weverything restrict.c -O3

I was expecting to see something, at least from one of the compilers, or
maybe from -fanalyzer, but to my surprise, this bug is completely
unnoticed; both in the call and in the definition.  It's time to file a
bug.

-- 
<https://www.alejandro-colomar.es/>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]