Y292B bug
26 June 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.
* 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.