Exploring the insides of Linux version 0.01
The Linux kernel is considered terribly large open source software. The latest version, 6.5-rc5, as of this writing, is 36 million lines of code. Of course, Linux is the fruit of many years of hard work of many contributors to the project.
However, the first version of Linux, v0.01, was quite small. It consisted of only 10239 lines of code. If comments and empty lines are excluded, then only 8670 lines remain. This is a fairly small amount of space for analysis and a good start for learning about the internals of the kernels of UNIX-like operating systems.
I enjoyed reading code v0.01. It was like visiting the Computer History Museum in Mountain View – I was finally convinced that legends true! I wrote this article to share this amazing experience with you.
Note: Obviously, I am not the author of Linux v0.01. If you find errors in the post, please let me know!
What do system calls look like?
v0.01 has 66 system calls. Here is their list:
access acct alarm break brk chdir chmod
chown chroot close creat dup dup2 execve
exit fcntl fork fstat ftime getegid geteuid
getgid getpgrp setsid getpid getppid
getuid gtty ioctl kill link lock lseek
mkdir mknod mount mpx nice open pause
phys pipe prof ptrace read rename rmdir
setgid setpgid setuid setup signal stat
stime stty sync time times ulimit umask
umount uname unlink ustat utime waitpid writeIt supports reading, writing and deleting files and folders. It also supports other fundamental concepts like
chmod(2)(permissions),chown(2)(owners) andpipe(2)(interaction between processes).fork(2)Andexecve(2)already exist. Only the executable file format is not supporteda.out.The concept of sockets is not implemented, which means no support for networks.
Some functions like
mount(2)not implemented. They only returnENOSYS:
int sys_mount()
{
return -ENOSYS;
}Deep hardcode for Intel 386 architecture
Linus had famous debate with MINIX author Andrew Tanenbaum on which is better for operating system architecture: a monolith or a microkernel?
Tanenbaum declaredthat Linux is not portable, because it is highly adapted to Intel 386 (i386):
MINIX was designed with reasonable portability in mind and has been ported from the Intel line to the 680×0 (Atari, Amiga, Macintosh), SPARC, and NS32016. LINUX is quite strongly tied to 80×86. This is the wrong way.
And indeed it is. Linux v0.01 has been heavily adapted for i386. Here is the implementation strcpy V include/string.h:
extern inline char * strcpy(char * dest,const char *src)
{
__asm__("cld\n"
"1:\tlodsb\n\t"
"stosb\n\t"
"testb %%al,%%al\n\t"
"jne 1b"
::"S" (src),"D" (dest):"si","di","ax");
return dest;
}It is written in assembly language with i386 string instructions. Yes, it can be found as an optimized implementation strcpy V modern Linuxbut she is in include/string.hnot somewhere like include/i386/string.h. Moreover, there are no #ifdef to switch implementations to other architectures. It’s just hardcode for Intel 386.
In addition, only PC/AT devices were supported:
CMOS: real time clock (
init/main.c).Programmable Interval Timer (PIT): timer (
kernel/sched.c).ATA (PIO): HDD (
kernel/hd.c).VGA (text mode): display (
kernel/console.c).Intel 8042: PS/2 keyboard (
kernel/keyboard.s). Yes, this implementation is written entirely in assembly language!
As you can see they are not in the folder driverslike in modern Linux. They are hardcoded into the basic subsystems.
FREAX
I read somewhere that Linus originally named his kernel “FREAX”. In Makefile linux v0.01 still has the following comment:
# Makefile for the FREAX-kernel.It really was FREAX!
What file system was supported in v0.01?
Today, Linux supports many file systems, such as ext4, Btrfs, and XFS. What about v0.01? ext2? No. IN include/linux/fs.h there is a hint:
#define SUPER_MAGIC 0x137FAs correctly guessed GPT-4This MINIX file system!
Fun fact: the inspiration for ext (“extended file system”, “extended file system”), the predecessor of ext2 / ext3 / ext4, became the MINIX file system.
“Most likely”, there will be no reason to change the scheduler
Here is the Linux scheduler v0.01:
while (1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c) break;
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
}
switch_to(next);
IN i And p task index in the task table (not PID!) and a pointer to the structure are stored task_struct. The most important variable is counter V task_struct ((*p)->counter). The scheduler takes the task with the highest value counter and switches to it. If all tasks that can be performed have counter values of 0, then it assigns the value counter each task counter = (counter >> 1) + priority and restarts the cycle. note that counter >> 1 is a faster way to divide by 2.
The most important point is updating the counter. It also updates the counter of tasks that cannot be performed. Also, this means that if a task is waiting for I/O for a long time, and its priority is higher than 2, then when the counter is updated, its value will increase to a certain upper limit. This is just my guess, but I think this is to prioritize infrequently executed but latency-sensitive tasks like the shell, which waits for keyboard input most of the time.
Finally, switch_to(next) is a macro that switches the CPU context to the selected task. He is well described Here. In short, it was based on an x86 specific feature called Task State Segment (TSS)which is no longer used for task management on the x86-64 architecture.
By the way, there is an interesting comment about the scheduler in the code:
* 'schedule()' - это функция планировщика. Это ХОРОШИЙ КОД! Скорее всего,
* не будет никаких причин менять её, она должна хорошо работать при всех
* условиях (например, она обеспечивает сильно зависящим от ввода-вывода
* процессам хорошее время отклика и тому подобное).
Yes, this is really good code. Unfortunately (or fortunately), this prophecy turned out to be wrong. Linux has become one of the most practical and high performing kernels, with many scheduling improvements and new algorithms over the years, such as the Completely Fair Scheduler (CFS).
Kernel panic in five lines
volatile void panic(const char * s)
{
printk("Kernel panic: %s\n\r",s);
for(;;);
}
We report that an error has occurred, and hang the system. Dot.
fork(2) in kernel space?
The bulk of the kernel initialization is in init/main.c (fun fact: this file is still in the modern Linux kernel and initializes the kernel):
void main(void) /* Это ДЕЙСТВИТЕЛЬНО void, тут нет никаких ошибок. */
{ /* Процедура запуска подразумевает, что */
/*
* Прерывания всё ещё отключены. Выполняет необходимую подготовку, затем
* включаем их
*/
time_init();
tty_init();
trap_init();
sched_init();
buffer_init();
hd_init();
sti();
move_to_user_mode();
if (!fork()) { /* мы рассчитываем, что это пройдёт без ошибок */
init();
}
/*
* ПРИМЕЧАНИЕ!! Для любой другой задачи 'pause()' будет означать, что
* нужно получить сигнал для пробуждения, но task0 - это единственное
* исключение (см. 'schedule()'), потому что task0 активируется в каждый
* момент простоя (когда не может выполняться ни одна другая задача)
* Для task0 'pause()' просто означает, что мы проверяем, может ли выполниться
* какая-то другая задача, и если нет, то мы возвращаемся сюда.
*/
for(;;) pause();
}
void init(void)
{
int i,j;
setup();
if (!fork())
_exit(execve("/bin/update",NULL,NULL));
(void) open("/dev/tty0",O_RDWR,0);
(void) dup(0);
(void) dup(0);
printf("%d buffers = %d bytes buffer space\n\r",NR_BUFFERS,
NR_BUFFERS*BLOCK_SIZE);
printf(" Ok.\n\r");
if ((i=fork())<0)
printf("Fork failed in init\r\n");
else if (!i) {
close(0);close(1);close(2);
setsid();
(void) open("/dev/tty0",O_RDWR,0);
(void) dup(0);
(void) dup(0);
_exit(execve("/bin/sh",argv,envp));
}
j=wait(&i);
printf("child %d died with code %04x\n",j,i);
sync();
_exit(0); /* ПРИМЕЧАНИЕ! _exit, а не exit() */
}This code calls the initialization functions of each subsystem, it’s pretty simple. But there is something interesting: it calls fork(2) V main() kernels. Besides, init() looks like a normal userspace implementation, but it’s hardcoded into the kernel code!
It looks like it’s fork(2) in kernel space, but it’s actually not. The trick here is move_to_user_mode():
#define move_to_user_mode() \
__asm__ ("movl %%esp,%%eax\n\t" \ // EAX = current stack pointer
"pushl $0x17\n\t" \ // SS (user data seg)
"pushl %%eax\n\t" \ // ESP
"pushfl\n\t" \ // EFLAGS
"pushl $0x0f\n\t" \ // CS (user code seg)
"pushl $1f\n\t" \ // EIP (return address)
"iret\n" \ // switch to user mode
"1:\tmovl $0x17,%%eax\n\t" \ // IRET returns to this address
"movw %%ax,%%ds\n\t" \ // Set DS to user data segment
"movw %%ax,%%es\n\t" \ // Set ES to user data segment
"movw %%ax,%%fs\n\t" \ // Set FS to user data segment
"movw %%ax,%%gs" \ // Set GS to user data segment
:::"ax") // No RET instruction here:
// continue executing following
// lines!We do not need to fully understand the assembly code presented above. It is enough to know that it switches to user mode with IRET commands , but continues to execute the next lines in the kernel code with the current stack pointer! Thus, the next if (!fork()) executed in user mode, and fork(2) it’s actually a system call.
Linus didn’t have a machine with 8 MB of RAM
* Если у вас больше 8 мб памяти, то вам не повезло. Если у меня её
* нет, почему у вас должна быть :-) Все исходники здесь, измените их.
* (Серьёзно - это не должно быть слишком сложно. ...
Today, machines with 8 GB of RAM are quite common. Moreover, 8 GB is not enough for software developers;)
Difficulty of compiling with modern toolchains
In the end, I tried to compile the kernel with modern toolchains, but I didn’t succeed. I thought GCC (or C itself) had good backwards compatibility, but it wasn’t enough. Even the old standard -std=gnu90 caused compilation errors that are not so easy to fix.
It’s funny that Linus used his own GCC with the key -mstring-insns:
# Если в вашем gcc нет '-mstring-insns' (а он есть только у меня :-)
# удалите его из директив define CFLAGS.
I don’t quite understand what it is, but it seems to be a feature to support (or optimize?) string commands x86.
If you manage to compile the kernel with modern toolchains, then write an article and send me a link.
Read for yourself!
I hope you enjoyed reading the Linux v0.01 source code as much as I did. If you are interested in v0.01, then download tarball version v0.01 from kernel.org. It’s not that hard to read the code, especially if you’ve already read xv6. Linux v0.01 is minimalist but very well written.
