Observation of hysteresis in a GNU libc time conversion function

Observation of hysteresis in a GNU libc time conversion function

[Max Nikulin]

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

#+title: Observation of hysteresis in a GNU libc time conversion function

#+begin_abstract
The ~mktime~ function in GNU libc for specific arguments
may possess properties similar to ferromagnetic materials.
Dependence of returned value on arguments passed during
earler calls gives evidences that it has hidden state.
#+end_abstract

I was experimenting with a code sample posted to the thread on
support of time zones in Org. I noticed rather strange behavior
of ~encode-time~ and thus underlying ~mktime~ function.
At first I considered it as non-deterministic, but later
I realized that time zone offset calculated earlier
may affect following calls. I was aware that the function is
not pure since it calls ~tzset~ to initialize time zone from
the ~TZ~ environment variable and e.g. ~tzname~ global variable.
It was a surprise that the function can not be considered
even as a stable one. Passing same arguments may lead
to different results. I am unsure whether it is intentional
or at least known property.

#+begin_src elisp :exports nil :results silent
   (require 'ob-shell)
   (require 'ob-gnuplot)
#+end_src

Let's take some backward time transition, so with ambiguous local time,
where daylight saving time state is not changed and preferably
is not in action. As a result it is impossible to disambiguate
whether local time is before or after time jump.
Attempt to specify ~dst~ as ~t~
(or set ~t.tm_isdst = 1~ for ~mktime~) will lead to an error.

#+begin_src sh :results verbatim :exports both
   zdump -v Africa/Juba | grep 2021
#+end_src

#+RESULTS:
: Africa/Juba  Sun Jan 31 20:59:59 2021 UT = Sun Jan 31 23:59:59 2021 
EAT isdst=0 gmtoff=10800
: Africa/Juba  Sun Jan 31 21:00:00 2021 UT = Sun Jan 31 23:00:00 2021 
CAT isdst=0 gmtoff=7200

We may convert broken down local time representation
around 23:30 local time
for a sequence of time moments passing values to ~encode-time~
in increasing and decreasing their order.
Under the hood the function calls the =mktime(3)= function.

#+name: timestamp
#+header: :exports code
#+begin_src elisp :var tz="Africa/Juba" :var t0='(0 30 23 31 1 2021)
     (let* ((f (lambda (minutes)
		(float-time
		 (encode-time
		  (list (nth 0 t0) (+ (nth 1 t0) minutes) (nth 2 t0)
			(nth 3 t0) (nth 4 t0) (nth 5 t0)
			nil -1 tz)))))
	   (dt '(-90 -60 -31 -30 -29 -15 0 15 29 30 31 60 90))
	   (values (mapcar (lambda (m)
			     (cons m (funcall f m)))
			   dt))
	   (ts0 (cdr (nth (/ (length values) 2) values))))
       (mapcar (lambda (pair)
		(let ((m (car pair)))
		  (list m (- (cdr pair) ts0) (- (funcall f m) ts0))))
	      (reverse values)))
#+end_src

#+RESULTS: timestamp
|  90 |  9000.0 |  9000.0 |
|  60 |  7200.0 |  7200.0 |
|  31 |  5460.0 |  5460.0 |
|  30 |  5400.0 |  5400.0 |
|  29 |  1740.0 |  5340.0 |
|  15 |   900.0 |  4500.0 |
|   0 |     0.0 |  3600.0 |
| -15 |  -900.0 |  2700.0 |
| -29 | -1740.0 |  1860.0 |
| -30 | -1800.0 |  1800.0 |
| -31 | -1860.0 | -1860.0 |
| -60 | -3600.0 | -3600.0 |
| -90 | -5400.0 | -5400.0 |

#+begin_src gnuplot :file mktime-hyst.png :var data=timestamp
   set key bottom right
   set xlabel 'minutes'
   set ylabel 'UNIX epoch difference, seconds'
   set title 'Hysteresis in GNU libc mktime'
   plot data using 1:2 with lp title 'increasing', \
      '' using 1:3 with lp title 'decreasing'
#+end_src

#+RESULTS:
[[file:mktime-hyst.png]]

So result for the same arguments may depend on previous calls.

Likely it is due to a
[[https://sourceware.org/git/?p=glibc.git;a=blob;f=time/mktime.c;h=94a4320e6ca9d935fc534991f9b57a2f1cc185de;hb=HEAD#l544][static 
variable]]
used in the =mktime.c= file. Such a variable appeared in the commit
[[https://sourceware.org/git/?p=glibc.git;a=commit;h=80fd73873b][80fd73873b]]
#+begin_example
Fri Sep 29 03:43:51 1995  Paul Eggert

Rewrite mktime from scratch for performance, and for correctness
in the presence of leap seconds.
#+end_example

Perhaps hidden internal state may be used to disambiguate local
time values around backward time steps with unchanged daylight
saving time. Unfortunately relying on such implementation details
hardly can be considered as a robust approach.

[-- Attachment #2: mktime-hyst.png --]
[-- Type: image/png, Size: 7420 bytes --]

Re: Observation of hysteresis in a GNU libc time conversion function

[Ihor Radchenko]

Max Nikulin <manikulin@gmail.com> writes:

> 	   (dt '(-90 -60 -31 -30 -29 -15 0 15 29 30 31 60 90))

This is problematic. You are putting MINUTES out of normal range.
Looking at
https://codecogs.com/library/computing/c/time.h/ctime.php?alias=mktime,
out-of-range minutes are not documented.

Also, see
https://stackoverflow.com/questions/20104531/weird-mktime-logic-with-negative-seconds

Using out-of-range time fields is not advised.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Observation of hysteresis in a GNU libc time conversion function

[Max Nikulin]

On 18/01/2023 16:54, Ihor Radchenko wrote:
> Max Nikulin writes:
> 
>> 	   (dt '(-90 -60 -31 -30 -29 -15 0 15 29 30 31 60 90))
> 
> This is problematic. You are putting MINUTES out of normal range.

Actually after some experiments and surprising results I figured out 
what really happens. I modified your example to get the value that you 
was likely expecting:

(let* ((tz "Europe/Berlin")
        (t1 (encode-time `(0 1 3 29 10 2023 nil -1 ,tz)))
        ;; !!! Try to comment out the line below
        (_ (encode-time `(0 59 1 29 10 2023 nil -1 ,tz)))
        (t2 (encode-time `(0 59 2 29 10 2023 nil -1 ,tz))))
   (list
    (format-time-string "%F %T %z %Z" t1 tz)
    (format-time-string "%F %T %z %Z" t2 tz)
    (time-subtract t1 t2)))
("2023-10-29 03:01:00 +0100 CET" "2023-10-29 02:59:00 +0200 CEST" 3720)

No negative minutes were involved.

I decided that hysteresis example is more funny.

Frankly speaking, I just forgot that I may use (make-decoded-time 
:minute -40) and `decoded-time-add' since I was not limited by Emacs-26 
support.

`encode-time' docstring for Emacs-26 has the following statement:

> Out-of-range values for SECOND, MINUTE, HOUR, DAY, or MONTH are allowed;
> for example, a DAY of 0 means the day preceding the given month.

So I do not think it affects anything. I decided to ask GNU libc developers
https://inbox.sourceware.org/libc-alpha/tq93sc$p3$1@ciao.gmane.io/T/#u
"mktime result may depend on previous calls"

> Looking at
> https://codecogs.com/library/computing/c/time.h/ctime.php?alias=mktime,
> out-of-range minutes are not documented.

Looks like a compilation of unspecified sources. The following is 
similar to ctime(3) man page

   if structure members are outside their valid
   interval,  they will be normalized (so that, for example,
   40 October is changed into 9 November);

My reading is that out of range values for other "members" are allowed 
as well. However it may be tricky.

> Also, see
> https://stackoverflow.com/questions/20104531/weird-mktime-logic-with-negative-seconds

My expectation is that ±1 day (or month) should preserve local time 
hours (e.g. 11:00 CET -> 11:00 CEST) if such moment of time exists. ±24 
hours, ±24*60 minutes, ±24*3600 seconds across DST change should cause 
appropriate shift of hours (e.g. 11:00 -> 12:00 is possible).

Moreover "out of range" month day 0 is the only way to specify last 
month day to get

      Jan, 31 <- 1 month -> Feb, 28 (or 29) <- 1 month -> Mar, 31

arithmetic.

However it is hardly implementation specific and GNU date(1) CLI 
utility, PostgreSQL, PHP timelib, JavaScript Date objects behave 
differently.

I still do not think it affects my example though.

Re: Observation of hysteresis in a GNU libc time conversion function

[Max Nikulin]

> On 18/01/2023 16:54, Ihor Radchenko wrote:
>>
>> This is problematic. You are putting MINUTES out of normal range. 

<info:libc#Broken-down Time> (Isn't it really broken?)
https://www.gnu.org/software/libc/manual/html_node/Broken_002ddown-Time.html

>  It uses the values of the other components to determine the calendar
> time; it’s permissible for these components to have unnormalized values
> outside their normal ranges.

Re: Observation of hysteresis in a GNU libc time conversion function

[Ihor Radchenko]

Max Nikulin <manikulin@gmail.com> writes:

>> Also, see
>> https://stackoverflow.com/questions/20104531/weird-mktime-logic-with-negative-seconds
>
> My expectation is that ±1 day (or month) should preserve local time 
> hours (e.g. 11:00 CET -> 11:00 CEST) if such moment of time exists. ±24 
> hours, ±24*60 minutes, ±24*3600 seconds across DST change should cause 
> appropriate shift of hours (e.g. 11:00 -> 12:00 is possible).
>
> Moreover "out of range" month day 0 is the only way to specify last 
> month day to get
>
>       Jan, 31 <- 1 month -> Feb, 28 (or 29) <- 1 month -> Mar, 31
>
> arithmetic.

Can we expect the same to work on Windows? If so, maybe we don't need
all the dancing around rounding off in `org-timestamp-change' and
instead simply use time API?

Re: 11:00 CET -> 11:00 CEST

Note that Org does not exactly offer much of convenience even without
considering TZ.

<2023-01-31 Thu +1m> -> <2023-03-03 Fri +1m>
And nobody really complained so far.
So, maybe we don't even need to care about these subtleties in practice?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>