Исследуем внутренности Linux версии 0.01

Ядро Linux считается ужасно масштабным опенсорсным ПО. Последняя на момент написания этой статьи версия 6.5-rc5 состоит из 36 миллионов строк кода. Само собой, Linux — это плод упорного многолетнего труда множества участников проекта.

Однако первая версия Linux, v0.01, была довольно маленькой. Она состояла всего из 10239 строк кода. Если исключить комментарии и пустые строки, то остаётся всего 8670 строк. Это достаточно малый объём для анализа и хорошее начало для изучения внутренностей ядер UNIX-подобных операционных систем.

Я получил удовольствие от чтения кода v0.01. Это походило на посещение Музея компьютерной истории в Маунтин-Вью — я наконец-то убедился, что легенды верны! Я написал эту статью, чтобы поделиться с вами этим восхитительным опытом.

Примечание: очевидно, я не автор Linux v0.01. Если найдёте в посте ошибки, то дайте мне знать об этом!

Как выглядят системные вызовы?

v0.01 имеет 66 системных вызовов. Вот их список:

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 write

• Она поддерживает чтение, запись и удаление файлов и папок. Также поддерживаются другие фундаментальные концепции наподобие chmod(2) (разрешений), chown(2) (владельцев) и pipe(2) (взаимодействие между процессами).

• fork(2) и execve(2) уже существуют. Не поддерживается только формат исполняемых файлов a.out.

• Концепция сокетов не реализована, а значит, никакой поддержки сетей.

• Некоторые функции наподобие mount(2) не реализованы. Они лишь возвращают ENOSYS:

int sys_mount()
{
	return -ENOSYS;
}

Глубокий хардкод под архитектуру Intel 386

У Линуса были знаменитые дебаты с автором MINIX Эндрю Таненбаумом о том, что же лучше подходит для архитектуры операционных систем: монолит или микроядро?

Таненбаум заявил, что Linux не портируем, потому что сильно адаптирован под Intel 386 (i386):

MINIX проектировалась с расчётом на разумную портируемость и была портирована с линейки Intel на 680x0 (Atari, Amiga, Macintosh), SPARC и NS32016. LINUX достаточно сильно привязан к 80x86. Это ошибочный путь.

И это действительно так. Linux v0.01 была сильно адаптирована под i386. Вот реализация strcpy в include/string.h:

extern inline char * strcpy(char * dest,const char *src)
{
__asm__("cldn"
	"1:tlodsbnt"
	"stosbnt"
	"testb %%al,%%alnt"
	"jne 1b"
	::"S" (src),"D" (dest):"si","di","ax");
return dest;
}

Она написана на языке ассемблера со строковыми командами i386. Да, её можно найти в качестве оптимизированной реализации strcpy в современном Linux, но она находится в include/string.h, а не где-то типа include/i386/string.h. Более того, там нет никаких #ifdef для переключения реализации под другие архитектуры. Это просто хардкод под Intel 386.

Кроме того, поддерживались только устройства PC/AT:

• CMOS: часы реального времени (init/main.c).

• Programmable Interval Timer (PIT): таймер (kernel/sched.c).

• ATA (PIO): жёсткий диск (kernel/hd.c).

• VGA (text mode): дисплей (kernel/console.c).

• Intel 8042: клавиатура PS/2 (kernel/keyboard.s). Да, эта реализация полностью написана на языке ассемблера!

Как можно заметить, что они не находятся в папке drivers, как в современном Linux. Они жёстко прописаны в базовых подсистемах.

«FREAX»

Я где-то читал, что изначально Линус назвал своё ядро «FREAX». В Makefile Linux v0.01 всё ещё есть следующий комментарий:

# Makefile for the FREAX-kernel.

Это действительно был FREAX!

Какая файловая система поддерживалась в v0.01?

Сегодня Linux поддерживает множество файловых систем, например ext4, Btrfs и XFS. А как насчёт v0.01? ext2? Нет. В include/linux/fs.h есть подсказка:

#define SUPER_MAGIC 0x137F

Как правильно предположил GPT-4, это файловая система MINIX!

Забавный факт: источником вдохновения для ext («extended file system», «расширенной файловой системы»), предшественницы ext2/ext3/ext4, стала файловая система MINIX.

«Скорее всего», не будет никаких причин менять планировщик

Вот планировщик Linux 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);

В i и p хранятся индекс задачи в таблице задач (не PID!) и указатель на структуру task_struct. Самая важная переменная — это counter в task_struct ((*p)->counter). Планировщик берёт задачу с наибольшим значением counter и переключается на неё. Если все задачи, которые можно выполнять, имеют значения счётчика 0, то он присваивает значению  counter каждой задачи counter = (counter >> 1) + priority и перезапускает цикл. Обратите внимание, что counter >> 1  — это более быстрый способ деления на 2.

Самый важный момент — это обновление счётчика. Оно также обновляет значение счётчика задач, которые нельзя выполнять. Кроме того, это означает, что если задача ожидает ввода-вывода долго, а её приоритет выше 2, то при обновлении счётчика его значение будет увеличиваться до определённого верхнего предела. Это всего лишь моя догадка, но я думаю, что это нужно для повышения приоритета редко выполняемых, но чувствительных к задержкам задач наподобие оболочки, которая бОльшую часть времени ожидает ввода с клавиатуры.

Наконец, switch_to(next) — это макрос, переключающий контекст CPU на выбранную задачу. Он хорошо описан здесь. Если вкратце, он был основан на специфической особенности x86 под названием Task State Segment (TSS), которая больше не используется для управления задачами в архитектуре x86-64.

Кстати, о планировщике в коде есть интересный комментарий:

 *  'schedule()' - это функция планировщика. Это ХОРОШИЙ КОД! Скорее всего,
 * не будет никаких причин менять её, она должна хорошо работать при всех
 * условиях (например, она обеспечивает сильно зависящим от ввода-вывода
 * процессам хорошее время отклика и тому подобное).

Да, это действительно хороший код. К сожалению (или к счастью), это пророчество оказалось ошибочным. Linux стал одним из самых практичных и высокопроизводительных ядер, в которое за много лет внесли множество улучшений планирования и новые алгоритмы, например Completely Fair Scheduler (CFS).

Kernel panic в пяти строках

volatile void panic(const char * s)
{
	printk("Kernel panic: %snr",s);
	for(;;);
}

Сообщаем, что произошла ошибка, и вешаем систему. Точка.

fork(2) в пространстве ядра?

Основная часть инициализации ядра находится в init/main.c (любопытный факт: этот файл по-прежнему находится в современном ядре Linux и инициализирует ядро):

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 spacenr",NR_BUFFERS,
		NR_BUFFERS*BLOCK_SIZE);
	printf(" Ok.nr");
	if ((i=fork())<0)
		printf("Fork failed in initrn");
	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 %04xn",j,i);
	sync();
	_exit(0);	/* ПРИМЕЧАНИЕ! _exit, а не exit() */
}

Этот код вызывает функции инициализации каждой подсистемы, всё довольно просто. Но есть и нечто интересное: он вызывает fork(2) в main() ядра. Кроме того, init() выглядит как обычная реализация в пользовательском пространстве, но она жёстко прописана в коде ядра!

Похоже, что она выполняет fork(2) в пространстве ядра, но на самом деле это не так. Хитрость здесь заключается в move_to_user_mode():

#define move_to_user_mode() 
__asm__ ("movl %%esp,%%eaxnt"  // EAX = current stack pointer
	"pushl $0x17nt"            // SS (user data seg)
	"pushl %%eaxnt"            // ESP
	"pushflnt"                 // EFLAGS
	"pushl $0x0fnt"            // CS (user code seg)
	"pushl $1fnt"              // EIP (return address)
	"iretn"                     // switch to user mode
	"1:tmovl $0x17,%%eaxnt"   // IRET returns to this address
	"movw %%ax,%%dsnt"         // Set DS to user data segment
	"movw %%ax,%%esnt"         // Set ES to user data segment
	"movw %%ax,%%fsnt"         // Set FS to user data segment
	"movw %%ax,%%gs"             // Set GS to user data segment
	:::"ax")                      // No RET instruction here: 
                                  // continue executing following
                                  // lines!

У нас нет необходимости полностью понимать представленный выше ассемблерный код. Достаточно знать, что он переключается в пользовательский режим при помощи команды IRET , но продолжает исполнять следующие строки в коде ядра с текущим указателем стека! Таким образом, последующий if (!fork()) исполняется в пользовательском режиме, а fork(2) на самом деле — это системный вызов.

У Линуса не было машины с 8 МБ ОЗУ

 * Если у вас больше 8 мб памяти, то вам не повезло. Если у меня её
 * нет, почему у вас должна быть :-) Все исходники здесь, измените их.
 * (Серьёзно - это не должно быть слишком сложно. ...

Сегодня довольно широко распространены машины с 8 ГБ ОЗУ. Больше того, 8 ГБ для разработчиков ПО совсем мало ;)

Сложность компиляции современными тулчейнами

В конце я попытался скомпилировать ядро с помощью современных тулчейнов, но мне не удалось. Я думал, что GCC (или сам C) обладает хорошей обратной совместимостью, но её оказалось недостаточно. Даже старый стандартный -std=gnu90 вызывал ошибки компиляции, которые не так уж легко устранить.

Забавно, что Линус использовал собственный GCC с ключом -mstring-insns:

# Если в вашем gcc нет '-mstring-insns' (а он есть только у меня :-)
# удалите его из директив define CFLAGS.

Не совсем понимаю, что это, но, похоже, это функция для поддержки (или оптимизации?) строковых команд x86.

Если вам удастся скомпилировать ядро современными тулчейнами, то напишите статью и отправьте мне ссылку.

Прочитайте сами!

Надеюсь, чтение исходного кода Linux v0.01 понравилось вам так же, как и мне. Если вас интересует v0.01, то скачайте tarball версии v0.01 с kernel.org. Читать код не так сложно, особенно если вы уже читали xv6. Linux v0.01 минималистичен, но очень хорошо написан.