## Y292B bug

*26 Jun 2024 - We're doomed! Again...*

Timekeeping is bitch. I found out the hard way while trying to program extendable time keeper for other celestial bodies in the Solar system. The problem is that, every calendar system is flooded with so many rules and exceptions that the calendar builder basically becomes another programming language. I am well aware of the Zawinski's Law* however, I wanted to avoid creating another Emacs.

Common timekeeping obstacles include inconsistent leap intervals,
ever changing time zones and conversions from one timekeeping system to another.
In addition to these algorithmic problems, there are device limitations
like precision of the oscilator or memory capacity.
In modern age, these are usually overlooked, especially memory allocation
is not considered a serious problem since the *Y2K bug* came and went.

*Y2K*, *Y2038* and other Y2xx bugs are not really "bugs" but
simple overflow of reserved memory space. You see, Unix and unix-like
computer systems measure time by incrementing seconds in single integer
variable *time_t*. Naturally, this timekeeping is named the *Unix time*
and its 0 is equal to midnight, 1st of January 1970.

Different
implementations of the Unix time, use different data type for *time_t*.
When the data type reaches its upper limit, it will "flip", either
to its opposite (negative) value or to the 0.
Current, main branch of the Linux kernel and uses signed 64-bit integer.
This solution has rollover point in year 292,277,026,596.
That is roughly 292 billion, 277 million, 24 thousand years into future.

The number overflows and the date will jump back 278 billion years before the Big Bang**? Needles to say, this needs to be fixed. Luckily, we have 33 life times of our Sun to solve this problem but we could propose some solutions even today. The obvious solution is to use dynamically typed language.

use strict;

use warnings;

my $time_f = 9223372036854775809; # out of long int range

my $year_s = 31536000; # seconds in year

while (1) {

my $year = int($time_f / $year_s + 1970);

print "unix time: $time_f \tyear: $year\n";

$time_f++;

#sleep(1);

}

Problem solved. Devoted fans of parentheses can use Lisp. Now the variable will increment indefinitely with
only limitation being the physical memory. The *time_f* (f stands for fix)
can consist of slightly over 1 billion *digits* per 1GB of memory. However, Linus Torvalds would rather
use Debian than program in anything other than C, so if we want to put this into
the kernel, we need to get more static.

#include <stdlib.h>

#include <string.h>

#include <gmp.h> // GNU Multiple Precision Arithmetic Library

int main() {

mpz_t time_f, year_s, year;

mpz_init(time_f);

mpz_init(year_s);

mpz_init(year);

mpz_set_str(time_f, "9223372036854775809", 10); // out of long int range

mpz_set_str(year_s, "31536000", 10); // seconds in year

while (1) {

mpz_tdiv_q(year, time_f, year_s);

gmp_printf("unix time: %Zd", time_f);

gmp_printf("\t\tyear: %Zd\n", year);

// Increment unix time by 1

mpz_add_ui(time_f, time_f, 1);

}

return 0;

}

In C, we can utilize the *GNU Multiple Precision Arithmetic Library*
which will allow us to dynamically allocate memory for variables.
Unfortunately, the *gmp.h* is not compatible with kernel space, so
we will need to design this heresy from scratch.

For dynamic memory allocation in C we can use arrays. Then with strings
we can read
numbers beyond *long long int* just like with the *gmp.h*.
It would be also nice to create a division function for converting
seconds into reasonable time units, like years.

Let the structure *BigInt* represent large integers with arbitrary
precision using an array of digits.

int *digits; // Pointer to an array of digits

int size; // Number of digits

} BigInt;

Then we need to initialize the *BigInt* from the string input.

int len = strlen(str); // Get the length of the string

BigInt num; // Declare a BigInt variable

num.size = len; // Set the size of BigInt to the length of the string

num.digits = (int *)malloc(len * sizeof(int)); // Alloc memory for the digits

for (int i = 0; i < len; i++) {

num.digits[i] = str[len - 1 - i] - '0'; // Convert digits to int and store them in reverse

}

return num; // Return the initialized BigInt

}

And of course, we need to free the memory like all good mannered people.

free(num->digits);

num->digits = NULL;

num->size = 0;

}

When we have our structures fully defined, we will use them to feed variables with values.

BigInt time_f = loadCurrentUnixTime();

BigInt year_s = initBigInt("31536000"); // Seconds in a year

...

Now we can focus on the long division. This part was little bit problematic for me because of two reasons. C isn't my preferred language*** and as I found out, the long division is tought differently all over this planet. It seems that I have learnt the Germanic-Euroasian method which is little bit different than the method tought in english speaking countries. (Turns out, math ain't such universal language after all...) Anyway, with the help of my elementary school notes and one C book from local library, I managed to spit out next division function.

// Initialize result size and allocate memory for its digits

result->size = dividend->size;

result->digits = (int *)calloc(result->size, sizeof(int));

// Initialize help BigInt named current

BigInt current;

current.size = 0;

current.digits = (int *)calloc(dividend->size, sizeof(int));

// Fill the "current" helper var

for (int i = dividend->size - 1; i >= 0; i--) {

// Shift digits in the "current" to the left

for (int j = current.size; j > 0; j--) {

current.digits[j] = current.digits[j - 1];

}

// Add the next digit from dividend to the "current"

current.digits[0] = dividend->digits[i];

current.size++;

// Remove leading zeros in the "current"

while (current.size > 1 && current.digits[current.size - 1] == 0) {

current.size--;

}

int count = 0;

// Do division until the "current" is less than the divisor

while (isGreaterOrEqual(¤t, divisor)) {

BigInt tempResult;

// Subtract divisor from the "current"

subtractBigInt(¤t, divisor, &tempResult);

free(current.digits);

current = tempResult;

count++;

}

// Store the quotient in the result

result->digits[i] = count;

}

// Remove leading zeros in the result

while (result->size > 1 && result->digits[result->size - 1] == 0) {

result->size--;

}

free(current.digits);

}

With addition of few more functions to monitor the progress, I was able to get output for current Unix time and fictional with over 400 digits too.

The next logical step would be to modify it to fit the *time.c* in the
Linux kernel, however, my knowledge of kernel-space programming is converging
to a zero. Also, I am not sure how will the division function handle
prime numbers larger than *long long int*.

Anyway, the *fixed.c* is published under GPLv3 and available
here
for anyone who wants to fix the Y292b problem on a kernel level for future
generations. Good luck and remember, the time is ticking.

### Update

*5 Jul 2024*

Usually, I tend not to update my blogs as I believe every post is a
product of its time and circumstances, but today I will be the George
Lucas of obscure web writings. My email inbox got quite flooded with all
kinds of responses to this *not* bug *not* fix proposition, so
I wanted to make some things straight.

First of all, the post was written with a funny attitude, but it is in no way meant to be a joke, parody, or insult. Quite a lot of people understood what I meant by this software complete solution to an integer overflow problem and the tradeoffs of it. I still believe that such a solution could be implemented in some optional kernel module. (And not only for timekeeping).

Secondly, I know the linked demo has some optimizations
to be done; for example, the digits of *BigInt* should be *byte*,
not *int*. However, I want to emphasize that this is just an
algorithmic demo, not finished code.

Lastly, I want to address something that was not mentioned many times but felt tough to read nevertheless. I was not ordering people to immediately start working on this. The sole reason why I posted this to the Linux Kernel Mailing List was to inspire people with sufficient skill in kernel space to look into this unconventional idea. And I still believe that there must be someone who will try this out of curiosity - like in the old days.

I hope this will make less people angry.

* Zawinski's Law is fictional law in computer science that mocks the inevitable feature creep, stating that every program will eventually try to read email. Please note that the law was formulated during 90's, hence the email feature. I also found good website with more computer science laws.

** In this vlog Mr. Tyson mentions that time is not really relevant before the Big Bang. He proposes that before this point, time as now known concept might not even exist. To me, it is very interesting to think about time this way.

*** Even though I can appreciate the speed and direct control of the code, I still want to write code that is little bit more intuitive. But since by that I mean Pearl, I guess this all boils down to a personal preference.