time code progress

time code progress

[Rich Felker]

Hi all,

I've been working, as promised, on the time code overhaul for the next
release of musl. The main issues it's intended to address are:

- complete lack of overflow handling in the present code
- lack of support for zoneinfo time zones

After trying various things, the design I think I've settled on has
the following properties:

- Internally, all POSIX times (seconds since epoch) are passed around
  as long long. This ensures that values derived from struct tm,
  timezone rules, etc. can never overflow, and allows overflow
  checking to be deferred until it's time to convert the value back
  into time_t. Without this design, handling the "partial years" at
  the edge of time_t overflow range is very difficult, as is handling
  the denormalized struct tm forms mktime is required to support and
  normalize (for instance, overflowing the year range by using a very
  large month number).

- Instead of converting back and forth to broken-down struct tm for
  applying timezone rules, the new code simply converts the
  combination of year and TZ rule string to a POSIX time within the
  given year at which the transition occurs. This value has type long
  long so that it cannot overflow even at the boundary years.
  Determining whether DST is in effect at a given time is simply a
  range comparison, just like the comparison that will be used for
  processing zoneinfo-format timezone rules.

- For years within the currently-reasonable range/32-bit time_t, the
  hot path for converting a year to seconds since the epoch involves
  no division. We can get away with >>2 and %3 since in the range
  [1901,2099] the leap year rule is simply that multiple-of-4 years
  are leap years. I would like it be able to have the compiler throw
  away the larger, slower, general-case code on 32-bit-time_t targets,
  but unfortunately the need to use long long internally to avoid
  difficult corner cases is precluding that.

- Any representable struct tm will successfully convert to time_t if
  and only if it represents a value of seconds-since-the-epoch that
  fits in time_t. Any representable time_t will successfully convert
  to struct tm if and only if it represents a (normalized) date and
  time representable in struct tm. The relevant functions will avoid
  setting errno except on error so that a caller can distinguish
  between a time_t value of -1 as a valid result and as an error.

I'm not yet sure whether the new code will be larger or smaller than
the old code. It should be considerably faster, and most importantly,
more correct.

Rich

Re: time code progress

[Rich Felker]

On Tue, Jul 16, 2013 at 03:45:53PM -0400, Rich Felker wrote:
> Hi all,
> 
> I've been working, as promised, on the time code overhaul for the next
> release of musl. The main issues it's intended to address are:

Committed. Please let me know what bugs you find. :-)

Rich

Re: time code progress

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2013-07-17 05:33:25 -0400]:
> Committed. Please let me know what bugs you find. :-)
> 

gcc found this:

diff --git a/src/time/__map_file.c b/src/time/__map_file.c
index b6bf272..b322f09 100644
--- a/src/time/__map_file.c
+++ b/src/time/__map_file.c
@@ -14,7 +14,7 @@ const char unsigned *__map_file(const char *pathname, size_t *size)
        if (fd < 0) return 0;
        if (!__syscall(SYS_fstat, fd, &st))
                map = __mmap(0, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
-       __syscall(SYS_close);
+       __syscall(SYS_close, fd);
        *size = st.st_size;
        return map == MAP_FAILED ? 0 : map;
 }


(i think it did not like the syscall arg counting in case of 0 args in
#define __SYSCALL_NARGS_X(a,b,c,d,e,f,g,h,n,...) n
#define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0)
)

Re: time code progress

[Jens Gustedt]

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

Hi,

Am Mittwoch, den 17.07.2013, 13:39 +0200 schrieb Szabolcs Nagy:
> (i think it did not like the syscall arg counting in case of 0 args in
> #define __SYSCALL_NARGS_X(a,b,c,d,e,f,g,h,n,...) n
> #define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0)
> )

yes, this is in fact not suitable to test for 0 args. For the
preprocessor 0 args basically doesn't exist, there is always one
argument, but which is empty.

If this is really needed, I could contribute a cooked down version
from P99 of an NARGS macro that could deal with such a case. Please
let me know.

Jens

-- 
:: INRIA Nancy Grand Est :: http://www.loria.fr/~gustedt/   ::
:: AlGorille ::::::::::::::: office Nancy : +33 383593090   ::
:: ICube :::::::::::::: office Strasbourg : +33 368854536   ::
:: ::::::::::::::::::::::::::: gsm France : +33 651400183   ::
:: :::::::::::::::::::: gsm international : +49 15737185122 ::



[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: time code progress

[Szabolcs Nagy]

* Jens Gustedt <jens.gustedt@inria.fr> [2013-07-17 14:09:38 +0200]:
> Am Mittwoch, den 17.07.2013, 13:39 +0200 schrieb Szabolcs Nagy:
> > (i think it did not like the syscall arg counting in case of 0 args in
> > #define __SYSCALL_NARGS_X(a,b,c,d,e,f,g,h,n,...) n
> > #define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0)
> > )
> 
> yes, this is in fact not suitable to test for 0 args. For the
> preprocessor 0 args basically doesn't exist, there is always one
> argument, but which is empty.
> 

note that the problem is not that __VA_ARGS__ is empty
(it's not, contrary to what i might implied), but that
if n becomes 0 (== __VA_ARGS__ expands to one argument),
then there is no more arguments in the __SYSCALL_NARGS_X
call to substitute for '...', so a simple fix would be

#define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0, tralala)

but i'm not sure if this should be fixed (this is internal
code and i think there are no 0 argument syscalls)

i just wanted to record how i found the close without fd issue
(which shows that some kind of type checking for syscall
arguments would help libc hacking.. but that's non-trivial
to do)

Re: time code progress

[Rich Felker]

On Wed, Jul 17, 2013 at 01:39:06PM +0200, Szabolcs Nagy wrote:
> * Rich Felker <dalias@aerifal.cx> [2013-07-17 05:33:25 -0400]:
> > Committed. Please let me know what bugs you find. :-)
> > 
> 
> gcc found this:
> 
> diff --git a/src/time/__map_file.c b/src/time/__map_file.c
> index b6bf272..b322f09 100644
> --- a/src/time/__map_file.c
> +++ b/src/time/__map_file.c
> @@ -14,7 +14,7 @@ const char unsigned *__map_file(const char *pathname, size_t *size)
>         if (fd < 0) return 0;
>         if (!__syscall(SYS_fstat, fd, &st))
>                 map = __mmap(0, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
> -       __syscall(SYS_close);
> +       __syscall(SYS_close, fd);
>         *size = st.st_size;
>         return map == MAP_FAILED ? 0 : map;
>  }

I'm glad to hear this is the worst bug found so far. :-)

> (i think it did not like the syscall arg counting in case of 0 args in
> #define __SYSCALL_NARGS_X(a,b,c,d,e,f,g,h,n,...) n
> #define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0)
> )

Odd. I think 0-arg syscall is used elsewhere and works, but I agree it
looks broken.

Rich

Re: time code progress

[Jens Gustedt]

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

Am Mittwoch, den 17.07.2013, 15:19 +0200 schrieb Szabolcs Nagy:
> note that the problem is not that __VA_ARGS__ is empty
> (it's not, contrary to what i might implied), but that
> if n becomes 0 (== __VA_ARGS__ expands to one argument),
> then there is no more arguments in the __SYSCALL_NARGS_X
> call to substitute for '...', so a simple fix would be
> 
> #define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0, tralala)

right, you always have the name of the syscall as first argument

> but i'm not sure if this should be fixed (this is internal
> code and i think there are no 0 argument syscalls)
> 
> i just wanted to record how i found the close without fd issue
> (which shows that some kind of type checking for syscall
> arguments would help libc hacking.. but that's non-trivial
> to do)

if there are really no 0 argument syscalls

#define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1, tralali, tralala)

would be an implementation of a first consistency test. But wait my
man page of syscall(2) already has an example of a 0 argument one.

Other consistency checks would probably a bit more difficult to
implement. I could imagine how to check for the number of arguments of
particular syscalls. Type checking would be more difficult, and would
probably need some maintenance.

Jens

-- 
:: INRIA Nancy Grand Est :: http://www.loria.fr/~gustedt/   ::
:: AlGorille ::::::::::::::: office Nancy : +33 383593090   ::
:: ICube :::::::::::::: office Strasbourg : +33 368854536   ::
:: ::::::::::::::::::::::::::: gsm France : +33 651400183   ::
:: :::::::::::::::::::: gsm international : +49 15737185122 ::



[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: time code progress

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2013-07-17 09:31:10 -0400]:
> I'm glad to hear this is the worst bug found so far. :-)
> 

here is another one:
posix seems to require EOVERFLOW when the result cannot be represented
(i cleaned up my mktime/gmtime test copied from libc-testsuit)

diff --git a/src/time/mktime.c b/src/time/mktime.c
index e38b461..ef1fb42 100644
--- a/src/time/mktime.c
+++ b/src/time/mktime.c
@@ -25,6 +25,6 @@ time_t mktime(struct tm *tm)
        return t;
 
 error:
-       errno = EINVAL;
+       errno = EOVERFLOW;
        return -1;
 }

Re: time code progress

[Rich Felker]

On Wed, Jul 17, 2013 at 03:39:35PM +0200, Jens Gustedt wrote:
> Am Mittwoch, den 17.07.2013, 15:19 +0200 schrieb Szabolcs Nagy:
> > note that the problem is not that __VA_ARGS__ is empty
> > (it's not, contrary to what i might implied), but that
> > if n becomes 0 (== __VA_ARGS__ expands to one argument),
> > then there is no more arguments in the __SYSCALL_NARGS_X
> > call to substitute for '...', so a simple fix would be
> > 
> > #define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1,0, tralala)
> 
> right, you always have the name of the syscall as first argument
> 
> > but i'm not sure if this should be fixed (this is internal
> > code and i think there are no 0 argument syscalls)
> > 
> > i just wanted to record how i found the close without fd issue
> > (which shows that some kind of type checking for syscall
> > arguments would help libc hacking.. but that's non-trivial
> > to do)
> 
> if there are really no 0 argument syscalls
> 
> #define __SYSCALL_NARGS(...) __SYSCALL_NARGS_X(__VA_ARGS__,7,6,5,4,3,2,1, tralali, tralala)

There are, e.g. getpid. So I'm not sure why this issue has never come
up before. I'm guessing you have a newer gcc that added a new warning
for it; my gcc does not seem to warn.

Anyway, I thought of the 0-arg issue back when I came up with these
macros, and it was resolved by always having the syscall number. But I
failed to realize there would be no arguments for the ... slot of
__SYSCALL_NARGS_X.

> implement. I could imagine how to check for the number of arguments of
> particular syscalls. Type checking would be more difficult, and would
> probably need some maintenance.

This might be more easily achieved with a grep recipe...

Rich

Re: time code progress

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2013-07-17 05:33:25 -0400]:
> Committed. Please let me know what bugs you find. :-)

in mktime the overflow check is not strictly ok,
time_t is signed so the check relies on signed overflow

	long long t = __tm_to_secs(tm);
	// ...
	if ((time_t)t != t) goto error;

i'm not sure how to do the check efficiently without
invoking ub, but at least this should be commented

time_t seem to be long on all supported platforms so this should work:

if (t>LONG_MAX || t<LONG_MIN) goto error;

Re: time code progress

[Rich Felker]

On Sat, Jul 20, 2013 at 03:11:06AM +0200, Szabolcs Nagy wrote:
> * Rich Felker <dalias@aerifal.cx> [2013-07-17 05:33:25 -0400]:
> > Committed. Please let me know what bugs you find. :-)
> 
> in mktime the overflow check is not strictly ok,
> time_t is signed so the check relies on signed overflow

A conversion is not an overflow. If the actual value does not fit, it
results in an implementation-defined value (of the destination type)
or an implementation-defined signal. I'm happy assuming our
implementation does not do the latter, and even that it performs the
conversion via modular reduction, but we don't need that assumption
here. The fact that, if t does not fit in time_t, then NO value of
type time_t can ever be equal to t, is all we need.

> time_t seem to be long on all supported platforms so this should work:
> 
> if (t>LONG_MAX || t<LONG_MIN) goto error;

And then we would have to fix it when we add x32...

Rich

Re: time code progress

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2013-07-19 21:22:26 -0400]:
> A conversion is not an overflow. If the actual value does not fit, it
> results in an implementation-defined value (of the destination type)

you are right
sorry for the noise

Re: time code progress

[Rich Felker]

On Sat, Jul 20, 2013 at 03:29:13AM +0200, Szabolcs Nagy wrote:
> * Rich Felker <dalias@aerifal.cx> [2013-07-19 21:22:26 -0400]:
> > A conversion is not an overflow. If the actual value does not fit, it
> > results in an implementation-defined value (of the destination type)
> 
> you are right
> sorry for the noise

No problem at all. I was actually very happy to see that somebody is
reviewing the time code. :-)

Rich

Re: time code progress

[Rob Landley]

On 07/16/2013 02:45:53 PM, Rich Felker wrote:
> Hi all,
> 
> I've been working, as promised, on the time code overhaul for the next
> release of musl. The main issues it's intended to address are:

This should be in the wiki somewhere. There should be a design section.

Rob

Re: time code progress

[Rich Felker]

On Mon, Jul 22, 2013 at 04:38:38PM -0500, Rob Landley wrote:
> On 07/16/2013 02:45:53 PM, Rich Felker wrote:
> >Hi all,
> >
> >I've been working, as promised, on the time code overhaul for the next
> >release of musl. The main issues it's intended to address are:
> 
> This should be in the wiki somewhere. There should be a design section.

Hmm, I was going to say "this belongs in the documentation", but the
wiki would be a great place to stage things that eventually belong in
the docs for 1.0.

Rich