proposition for fixing Y292B bug

proposition for fixing Y292B bug

[David Polakovic]

Hello dear developers and enthusiasts.

My name is David and recently I wrote a blog post about "necessity"
of fixing 64-bit signed integer overflow of time_t, sometime in year
292 billion. I proposed this to simply have software complete solution
for timekeeping. The blog had somewhat nice feedback and few people
told me to write to your mailing list.

As I mention in the list, I am no way experienced enough in kernel
space to turn this into full merge request, so I post it to you and
if anyone would like to build on this idea, it is GPLd for your convenience.

Any feedback is highly appreciated so please, include me in CC's.

The blog is written with funny attitude, but it is in no way meant to
be joke, parody or insult.
https://dpolakovic.space/blogs/y292b

The source code can be found here.
https://git.dpolakovic.space/?p=unix-time-fix;a=summary


Thank you for your time.

dpo

Re: proposition for fixing Y292B bug

[Bagas Sanjaya]

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

On Sun, Jun 30, 2024 at 10:05:18AM +0200, David Polakovic wrote:
> Hello dear developers and enthusiasts.
> 
> My name is David and recently I wrote a blog post about "necessity"
> of fixing 64-bit signed integer overflow of time_t, sometime in year
> 292 billion. I proposed this to simply have software complete solution
> for timekeeping. The blog had somewhat nice feedback and few people
> told me to write to your mailing list.
> 
> As I mention in the list, I am no way experienced enough in kernel
> space to turn this into full merge request, so I post it to you and
> if anyone would like to build on this idea, it is GPLd for your convenience.
> 
> Any feedback is highly appreciated so please, include me in CC's.
> 
> The blog is written with funny attitude, but it is in no way meant to
> be joke, parody or insult.
> https://dpolakovic.space/blogs/y292b

Reading your paper, it seems like the userspace solution is to introduce bigger
int type (i.e. int128/bigint); and you want the same to apply to kernel, right?
Also, if that happens, I think C also needs built-in bigint type.

Confused...

-- 
An old man doll... just what I always wanted! - Clara

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

Re: proposition for fixing Y292B bug

[David Polakovic]

Thanks for reply.

My proposed solution was to create this BigInt datatype, which
stores the value in array. The functions for division, multiplication,
addition, subtraction and comparison could be stored in separate
".h" library for manipulation with BigInt datatype. The paper speaks
more in detail.

And yes, this truly is an userspace solution, but for kernel space
implementation I have zero to none experience. Therefore I wrote
here.

dpo


On 6/30/24 15:41, Bagas Sanjaya wrote:
> On Sun, Jun 30, 2024 at 10:05:18AM +0200, David Polakovic wrote:
>> Hello dear developers and enthusiasts.
>>
>> My name is David and recently I wrote a blog post about "necessity"
>> of fixing 64-bit signed integer overflow of time_t, sometime in year
>> 292 billion. I proposed this to simply have software complete solution
>> for timekeeping. The blog had somewhat nice feedback and few people
>> told me to write to your mailing list.
>>
>> As I mention in the list, I am no way experienced enough in kernel
>> space to turn this into full merge request, so I post it to you and
>> if anyone would like to build on this idea, it is GPLd for your convenience.
>>
>> Any feedback is highly appreciated so please, include me in CC's.
>>
>> The blog is written with funny attitude, but it is in no way meant to
>> be joke, parody or insult.
>> https://dpolakovic.space/blogs/y292b
> Reading your paper, it seems like the userspace solution is to introduce bigger
> int type (i.e. int128/bigint); and you want the same to apply to kernel, right?
> Also, if that happens, I think C also needs built-in bigint type.
>
> Confused...
>

Re: proposition for fixing Y292B bug

[Bagas Sanjaya]

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

On Sun, Jun 30, 2024 at 05:27:24PM +0200, David Polakovic wrote:
> Thanks for reply.

Please don't top-post on LKML, reply inline with appropriate context
instead.

> 
> My proposed solution was to create this BigInt datatype, which
> stores the value in array. The functions for division, multiplication,
> addition, subtraction and comparison could be stored in separate
> ".h" library for manipulation with BigInt datatype. The paper speaks
> more in detail.
> 
> And yes, this truly is an userspace solution, but for kernel space
> implementation I have zero to none experience. Therefore I wrote
> here.

There was a proposal for adding 128-bit unsigned integer (see [1]).
The signed counterpart should be analogous.

Thanks.

[1]: https://lore.kernel.org/lkml/20220722145514.767592-1-alexandr.lobakin@intel.com/

-- 
An old man doll... just what I always wanted! - Clara

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

Re: proposition for fixing Y292B bug

[Alexander Lobakin]

From: Bagas Sanjaya <bagasdotme@gmail.com>
Date: Mon, 1 Jul 2024 16:07:48 +0700

> On Sun, Jun 30, 2024 at 05:27:24PM +0200, David Polakovic wrote:
>> Thanks for reply.
> 
> Please don't top-post on LKML, reply inline with appropriate context
> instead.
> 
>>
>> My proposed solution was to create this BigInt datatype, which
>> stores the value in array. The functions for division, multiplication,
>> addition, subtraction and comparison could be stored in separate
>> ".h" library for manipulation with BigInt datatype. The paper speaks
>> more in detail.

IRRC there is big integer type somewhere in either lib/ or crypto/,
I don't remember exactly. It's used only for crypto tho.

>>
>> And yes, this truly is an userspace solution, but for kernel space
>> implementation I have zero to none experience. Therefore I wrote
>> here.
> 
> There was a proposal for adding 128-bit unsigned integer (see [1]).
> The signed counterpart should be analogous.

I have generic 128-bit integer API/infra for the kernel in my internal
repo. I've been planning to upstream it for a couple years already, but
every time couldn't find a slot to do that.
I can upload it to my open GitHub, so that maybe someone else who needs
it could pick it up?

> 
> Thanks.
> 
> [1]: https://lore.kernel.org/lkml/20220722145514.767592-1-alexandr.lobakin@intel.com/

Thanks,
Olek

Re: proposition for fixing Y292B bug

[David Polakovic]

On 7/1/24 15:31, Alexander Lobakin wrote:
> From: Bagas Sanjaya <bagasdotme@gmail.com>
> Date: Mon, 1 Jul 2024 16:07:48 +0700
>
>> On Sun, Jun 30, 2024 at 05:27:24PM +0200, David Polakovic wrote:
>>> Thanks for reply.
>> Please don't top-post on LKML, reply inline with appropriate context
>> instead.
>>
>>> My proposed solution was to create this BigInt datatype, which
>>> stores the value in array. The functions for division, multiplication,
>>> addition, subtraction and comparison could be stored in separate
>>> ".h" library for manipulation with BigInt datatype. The paper speaks
>>> more in detail.
> IRRC there is big integer type somewhere in either lib/ or crypto/,
> I don't remember exactly. It's used only for crypto tho.
>
>>> And yes, this truly is an userspace solution, but for kernel space
>>> implementation I have zero to none experience. Therefore I wrote
>>> here.
>> There was a proposal for adding 128-bit unsigned integer (see [1]).
>> The signed counterpart should be analogous.
> I have generic 128-bit integer API/infra for the kernel in my internal
> repo. I've been planning to upstream it for a couple years already, but
> every time couldn't find a slot to do that.
> I can upload it to my open GitHub, so that maybe someone else who needs
> it could pick it up?
>
>> Thanks.
>>
>> [1]: https://lore.kernel.org/lkml/20220722145514.767592-1-alexandr.lobakin@intel.com/
> Thanks,
> Olek


I am not sure if I don't understand your solution, but extending the
memory designation from 64 to 128 bits, is another temporary
solution, which will again overflow one day.

The sole reason why I was proposing the new "BigInt" type was to
store each digit of the time_c as separate element of array, which
could be resized (added one digit) as needed. The only limit would
then be the physical amount of memory in the machine.

dpo

Re: proposition for fixing Y292B bug

[Theodore Ts'o]

On Wed, Jul 03, 2024 at 05:29:58PM +0200, David Polakovic wrote:
> 
> I am not sure if I don't understand your solution, but extending the
> memory designation from 64 to 128 bits, is another temporary
> solution, which will again overflow one day.
> 
> The sole reason why I was proposing the new "BigInt" type was to
> store each digit of the time_c as separate element of array, which
> could be resized (added one digit) as needed. The only limit would
> then be the physical amount of memory in the machine.

You state that you're not experienced enough to be able to send "a
merge request".  Fair enough; you also apparently don't know that
github merges is not how kernel patches are submitted, reviewed, and
integrated.

What you apparently don't appreciate it is that performance is
something that is critically important for the Linux kernel, and using
multiple precision integers is not really compatible with the best and
highest performance.  Computer Science is an engineering discipline,
and it's all about tradeoffs.  You could enginere a plane that can
travel faster than the speed of sound, but if that compromises fuel
efficiency and annoying people who are below its flight path, pursuing
speed at all costs is not going to lead to commercial success.
(Exhibit 1: The Concorde).

Similarly, trying to make sure that software will work in the year 292
Billion AD might not be all something that most people would consider
high priority.  After all, it's.... unlikely... that the x86_64
architecture will still be what we will be using 290 billion years
from now.  So if we need recompile the kernel sometime in the next 100
billion years for some new CPU architecture, and if it's unlikely that
hard drives brought brand new are likely to be still in operation a
decade or two from now --- there is plenty of time to evolve the
on-disk format before a billion years go by, let alone 100 billion or
200 billion years.

Finally, kernel development is driven by people who are willing to do
the work.  If you want to demonstrate that it's possible to use MP
integer mathematicswithout horribly comprmising performance, then you
need to do the work.  (BTW, if you don't know what the term "cache
line" means, then I encourage that you understand that first.)  But
dropping a pointer to a blog post and expecting that people to do your
homework for you is not really realistic.

Cheers,

					- Ted

Re: proposition for fixing Y292B bug

[David Polakovic]

On 7/4/24 19:49, Theodore Ts'o wrote:
> On Wed, Jul 03, 2024 at 05:29:58PM +0200, David Polakovic wrote:
>> I am not sure if I don't understand your solution, but extending the
>> memory designation from 64 to 128 bits, is another temporary
>> solution, which will again overflow one day.
>>
>> The sole reason why I was proposing the new "BigInt" type was to
>> store each digit of the time_c as separate element of array, which
>> could be resized (added one digit) as needed. The only limit would
>> then be the physical amount of memory in the machine.
> You state that you're not experienced enough to be able to send "a
> merge request".  Fair enough; you also apparently don't know that
> github merges is not how kernel patches are submitted, reviewed, and
> integrated.
>
> What you apparently don't appreciate it is that performance is
> something that is critically important for the Linux kernel, and using
> multiple precision integers is not really compatible with the best and
> highest performance.  Computer Science is an engineering discipline,
> and it's all about tradeoffs.  You could enginere a plane that can
> travel faster than the speed of sound, but if that compromises fuel
> efficiency and annoying people who are below its flight path, pursuing
> speed at all costs is not going to lead to commercial success.
> (Exhibit 1: The Concorde).
>
> Similarly, trying to make sure that software will work in the year 292
> Billion AD might not be all something that most people would consider
> high priority.  After all, it's.... unlikely... that the x86_64
> architecture will still be what we will be using 290 billion years
> from now.  So if we need recompile the kernel sometime in the next 100
> billion years for some new CPU architecture, and if it's unlikely that
> hard drives brought brand new are likely to be still in operation a
> decade or two from now --- there is plenty of time to evolve the
> on-disk format before a billion years go by, let alone 100 billion or
> 200 billion years.
>
> Finally, kernel development is driven by people who are willing to do
> the work.  If you want to demonstrate that it's possible to use MP
> integer mathematicswithout horribly comprmising performance, then you
> need to do the work.  (BTW, if you don't know what the term "cache
> line" means, then I encourage that you understand that first.)  But
> dropping a pointer to a blog post and expecting that people to do your
> homework for you is not really realistic.
>
> Cheers,
>
> 					- Ted

I appreciate your response, finally some thoughts on the proposition itself
and please let me clear something up. It was exactly as you said, an 
tradeoff
I considered worthy and I wasn't expecting anyone to do "my work".
I thought that someone, experienced enough, might find this worthy
of try.

However, I'll take your challenge, and I will try to do the work on my 
own, if no
one else will. Let's see where it will lead me.

dpo

Re: proposition for fixing Y292B bug

[Bagas Sanjaya]

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

On Thu, Jul 04, 2024 at 01:49:17PM -0400, Theodore Ts'o wrote:
> On Wed, Jul 03, 2024 at 05:29:58PM +0200, David Polakovic wrote:
> > 
> > I am not sure if I don't understand your solution, but extending the
> > memory designation from 64 to 128 bits, is another temporary
> > solution, which will again overflow one day.
> > 
> > The sole reason why I was proposing the new "BigInt" type was to
> > store each digit of the time_c as separate element of array, which
> > could be resized (added one digit) as needed. The only limit would
> > then be the physical amount of memory in the machine.
> 
> You state that you're not experienced enough to be able to send "a
> merge request".  Fair enough; you also apparently don't know that
> github merges is not how kernel patches are submitted, reviewed, and
> integrated.

tl;dr: Documentation/process/submitting-patches.rst.

> 
> What you apparently don't appreciate it is that performance is
> something that is critically important for the Linux kernel, and using
> multiple precision integers is not really compatible with the best and
> highest performance.  Computer Science is an engineering discipline,
> and it's all about tradeoffs.  You could enginere a plane that can
> travel faster than the speed of sound, but if that compromises fuel
> efficiency and annoying people who are below its flight path, pursuing
> speed at all costs is not going to lead to commercial success.
> (Exhibit 1: The Concorde).
> 
> Similarly, trying to make sure that software will work in the year 292
> Billion AD might not be all something that most people would consider
> high priority.  After all, it's.... unlikely... that the x86_64
> architecture will still be what we will be using 290 billion years
> from now.  So if we need recompile the kernel sometime in the next 100
> billion years for some new CPU architecture, and if it's unlikely that
> hard drives brought brand new are likely to be still in operation a
> decade or two from now --- there is plenty of time to evolve the
> on-disk format before a billion years go by, let alone 100 billion or
> 200 billion years.

That was what I thought when I first read this thread (good CS principle
but questionable from engineering perspective).

> 
> Finally, kernel development is driven by people who are willing to do
> the work.  If you want to demonstrate that it's possible to use MP
> integer mathematicswithout horribly comprmising performance, then you
> need to do the work.  (BTW, if you don't know what the term "cache
> line" means, then I encourage that you understand that first.)  But
> dropping a pointer to a blog post and expecting that people to do your
> homework for you is not really realistic.

Oh, I missed that "DIY" nature.

Thanks.

-- 
An old man doll... just what I always wanted! - Clara

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

Re: proposition for fixing Y292B bug

[H. Peter Anvin]

On July 3, 2024 8:29:58 AM PDT, David Polakovic <email@dpolakovic.space> wrote:
>On 7/1/24 15:31, Alexander Lobakin wrote:
>> From: Bagas Sanjaya <bagasdotme@gmail.com>
>> Date: Mon, 1 Jul 2024 16:07:48 +0700
>> 
>>> On Sun, Jun 30, 2024 at 05:27:24PM +0200, David Polakovic wrote:
>>>> Thanks for reply.
>>> Please don't top-post on LKML, reply inline with appropriate context
>>> instead.
>>> 
>>>> My proposed solution was to create this BigInt datatype, which
>>>> stores the value in array. The functions for division, multiplication,
>>>> addition, subtraction and comparison could be stored in separate
>>>> ".h" library for manipulation with BigInt datatype. The paper speaks
>>>> more in detail.
>> IRRC there is big integer type somewhere in either lib/ or crypto/,
>> I don't remember exactly. It's used only for crypto tho.
>> 
>>>> And yes, this truly is an userspace solution, but for kernel space
>>>> implementation I have zero to none experience. Therefore I wrote
>>>> here.
>>> There was a proposal for adding 128-bit unsigned integer (see [1]).
>>> The signed counterpart should be analogous.
>> I have generic 128-bit integer API/infra for the kernel in my internal
>> repo. I've been planning to upstream it for a couple years already, but
>> every time couldn't find a slot to do that.
>> I can upload it to my open GitHub, so that maybe someone else who needs
>> it could pick it up?
>> 
>>> Thanks.
>>> 
>>> [1]: https://lore.kernel.org/lkml/20220722145514.767592-1-alexandr.lobakin@intel.com/
>> Thanks,
>> Olek
>
>
>I am not sure if I don't understand your solution, but extending the
>memory designation from 64 to 128 bits, is another temporary
>solution, which will again overflow one day.
>
>The sole reason why I was proposing the new "BigInt" type was to
>store each digit of the time_c as separate element of array, which
>could be resized (added one digit) as needed. The only limit would
>then be the physical amount of memory in the machine.
>
>dpo
>

So now you are worried about the Y5e30 problem?!

You realize that you are now talking the orders of magnitude of time for which: 

"	The estimated time until most or all of the remaining 1–10% of stellar remnants not ejected from galaxies fall into their galaxies' central supermassive black holes. By this point, with binary stars having fallen into each other, and planets into their stars, via emission of gravitational radiation, only solitary objects (stellar remnants, brown dwarfs, ejected planetary-mass objects, black holes) will remain in the universe."

I genuinely thought this whole thread was a practical joke...

Re: proposition for fixing Y292B bug

[Bagas Sanjaya]

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

On Thu, Jul 04, 2024 at 07:59:13PM -0700, H. Peter Anvin wrote:
> On July 3, 2024 8:29:58 AM PDT, David Polakovic <email@dpolakovic.space> wrote:
> >I am not sure if I don't understand your solution, but extending the
> >memory designation from 64 to 128 bits, is another temporary
> >solution, which will again overflow one day.
> >
> >The sole reason why I was proposing the new "BigInt" type was to
> >store each digit of the time_c as separate element of array, which
> >could be resized (added one digit) as needed. The only limit would
> >then be the physical amount of memory in the machine.
> >
> >dpo
> >
> 
> So now you are worried about the Y5e30 problem?!
> 
> You realize that you are now talking the orders of magnitude of time for which: 
> 
> "	The estimated time until most or all of the remaining 1–10% of stellar remnants not ejected from galaxies fall into their galaxies' central supermassive black holes. By this point, with binary stars having fallen into each other, and planets into their stars, via emission of gravitational radiation, only solitary objects (stellar remnants, brown dwarfs, ejected planetary-mass objects, black holes) will remain in the universe."
> 
> I genuinely thought this whole thread was a practical joke...

And that's what I thought as unnecessary engineering churn...

-- 
An old man doll... just what I always wanted! - Clara

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