Y292B bug

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

TITLE

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 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.

But then what?

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.

	#!/usr/bin/perl

	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  <stdio.h>

#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.

	typedef struct {

	   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.

	BigInt initBigInt(const char *str) {

	   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.

	void freeBigInt(BigInt *num) {

	   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.

	int main() {

	   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.

	void divideBigInt(BigInt *dividend, BigInt *divisor, BigInt *result) {

           // 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(&current, divisor)) {

              BigInt tempResult;

              // Subtract divisor from the "current"

              subtractBigInt(&current, 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.