24 февр. 2011 г.

xv6 - учебная операционная система для курса 6.828 в MIT

В MIT'шном курсе "Разработка операционных систем" (Operating System Engineering) используется простая, учебная операционная система, названная xv6. На нее я наткнулся, читая пост "Примеры хорошого кода" в блоге "Программирование — это просто!".
Когда-то давно, на заре становления данного курса (тогда он был еще экспериментальным) студенты работали сразу с двумя операционными системами. Первая ОСь - Unix V6 Кернигана и Томпсона, использовалась на лекциях и была написана на каком-то диалекте языка C, существовавшем еще до издания Керниганом и Ритчи  своей книги, посвященной языку программирования C. Вдобавок ко всему прочему, этот Unix V6 работал на устаревшем оборудовании - PDP-11.
Была и вторая операционная система - Jos, которую студенты разрабатывали сами, дабы постичь премудрости курса. Система была на основе экзоядра и писалась под Intel x86.
Нет ничего хорошего в том, что студенты изучают две различные архитектуры одновременно, на курсе, отнюдь не посвященном архитектурам вычислительных систем и преподаватели решили написать xv6 - операционную систему, основанную на V6, но тем не менее написанную на C и работающую на x86 процессорах.

Продолжение истории
Первая версия xv6 была написана летом 2006 года. Тогда же и пошел процесс замены Unix V6 на новоявленную операционную систему. Некоторые части V6, не очень хорошо написанные, были полностью переписаны заново и включены в исходный код xv6. Также, в xv6 был включен код из NetBSD, Plan9 и разрабатываемой студентами Jos.

Немного о самой xv6
Ядро xv6 монолитное, как и в Unix V6. Операционная система работает на процессорах архитектуры x86 (Intel, про другие ничего не сказано). ОС рекомендуется запускать в Qemu или Bochs, про успешные запуски на реальном железе мне ничего не известно.
Каких либо "навороченных" драйверов, например для USB, не ищите - экран, клавиатура, да UART, вот и все драйвера. Для целей обучения, больше и не надо...

Компиляция и первый запуск
Сборка системы описана в файле README, поставляемом с исходниками. Для сборки под Unix-like системами используется GCC - достаточно запустить make. Если xv6 компилируется под MacOS на x86 процессоре, то надо использовать кросскомпилятор, создающий ELF бинарники под x86.
На моей Linux-системе компиляция завершилась неудачей:
gcc -m32 -Werror -Wall -o mkfs mkfs.c
In file included from mkfs.c:9:0:
stat.h:5:8: error: redefinition of ‘struct stat’
/usr/include/bits/stat.h:39:8: note: originally defined here
make: *** [mkfs] Error 1
Как видно, определение внутренней для xv6 структуры struct stat конфликтует с аналогичным определением где-то в одном из заголовочных файлов, включенных в mkfs.c до stat.h.
Как оказалось, заголовочный файл bits/stat.h подключается внутри заголовочного файла fcntl.h:
/* For XPG all symbols from <sys/stat.h> should also be available.  */
#if defined __USE_XOPEN || defined __USE_XOPEN2K8
# include <bits/types.h>         /* For __mode_t and __dev_t.  */
# define __need_timespec
# include <time.h>
# include <bits/stat.h>

/* ....skipped.... */
#endif
Чтобы система скомпилировалась можно просто отменить определения __USE_XOPEN*. Судя по коду mkfs.c, вряд ли нам необходимо то, что объявляется в приведенном отрывке файла fcntl.h...
Итак, для успешной компиляции xv6 нужно заменить директиву #include в файле mkfs.c на:
#if defined __USE_XOPEN || defined __USE_XOPEN2K8
# undef __USE_XOPEN
# undef __USE_XOPEN2K8
# include <fcntl.h>
# define __USE_XOPEN
# define __USE_XOPEN2K8
#else
# include <fcntl.h>
#endif
Конечно, можно было просто не подключать свой заголовочный файл stat.h и скопировать из него необходимые дефайны прямо в mkfs.c (структура из заголовочного файла в нем не используется), но как-то это не спортивно...
Для запуска системы под Qemu нужно выполнить make qemu. В случае с Bochs - make bochs и нажать c в открывшейся консоли. С Bochs проще отлаживать системы, но в случае с Qemu система будет работать быстрее, поэтому для первого раза я выбрал Qemu. К слову, в AUR ArchLinux'а есть сборка Qemu специально для курса 6.828, называется qemu-6828.
Итак, после выполнения всех необходимых команд, мы получаем работающую систему:
xv6 в Qemu
Вводить команды можно как непосредственно в консоли xv6, так и в том терминале, в котором была выполнена команда make qemu.
Все бинарники свалены в / и их увы крайне мало:
В первую очередь, мне захотелось разобраться как система запускает ту или иную команду. Хотелось разобраться в деталях.

Как происходит запуск исполняемых файлов в xv6

Итак, проследим всю цепочку на примере утилиты ls - от исполняемого файла на диске системы, до машинного кода в оперативной памяти, переданного на исполнение процессору.
Исходный код этой утилиты лежит в дереве исходных кодов xv6 в файле ls.c. ELF собирается следующими командами:
gcc -fno-pic -static -fno-builtin -fno-strict-aliasing -O2 -Wall -MD -ggdb -m32 -Werror -fno-stack-protector   -c -o ls.o ls.c
ld -m    elf_i386 -N -e main -Ttext 0 -o _ls ls.o ulib.o usys.o printf.o umalloc.o
objdump -S _ls > ls.asm
objdump -t _ls | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > ls.sym
Вначале gcc собирает объектный файл ls.o с кодом внутри, зависящим от места расположения (-fno-pic). Это значит, что наш код не может быть загружен в память по любому адресу - загрузчик не позаботится о превращении относительных адресов в абсолютные. Не зависящий от места расположения код используется, как правило, в динамических библиотеках, а их, как видно на скриншоте выше, у нас нет.
И именно поэтому мы собираем статичный бинарник (-static) - некому и нечему загружать динамические библиотеки в память и вызывать функции из них.
Остальные опции отключают ненужные оптимизации GCC и дополнительный код для защиты от атак типа "переполнение буфера". Подробнее о данных опциях рекомендую читать в info gccman gcc информация неполная).
После того, как мы получили объектный файл ls.o, мы линкуем его с библиотечными объектными файлами в исполняемый файл _ls формата ELF под i386 процессор. Дополнительно мы указываем, что исполнение программы начинается сразу с символа "main" (-e main), а сегмент кода начинается с адреса 0x00 (-Ttext 0).
Полученный исполняемый файл _ls, вместе c остальными исполняемыми файлами, попадает в образ файловой системы, при этом префикс "_" удаляется утилитой mkfs:
UPROGS=\
    _cat\
    _echo\
    _forktest\
    _grep\
    _init\
    _kill\
    _ln\
    _ls\
    _mkdir\
    _rm\
    _sh\
    _stressfs\
    _usertests\
    _wc\
    _zombie\

fs.img: mkfs README $(UPROGS)
    ./mkfs fs.img README $(UPROGS)
Полученный образ используется впоследствии qemu как диск для нашей системы.

Когда мы нажимаем на клавиши чтобы ввести команду, процессору приходит прерывание от клавиатуры. Но задолго до того, как пользователь нажмет на кнопку на клавиатуре, происходит инициализация таблицы векторов прерываний, по которой будут вызываться обработчики для каждого из прерываний. Инициализация этой таблицы проводится функцией tvinit() (trap.c), которая вызывается внутри функции mainc() (файл main.c). Таблица векторов прерываний лежит внутри массива extern uint vectors[];, который определен внутри файла vectors.S как:
.globl alltraps
.globl vector0
vector0:
  pushl $0
  pushl $0
  jmp alltraps
;...
;==========skipped=========
;...
.globl vector255
vector255:
  pushl $0
  pushl $255
  jmp alltraps

# vector table
.data
.globl vectors
vectors:
  .long vector0
  .long vector1
  .long vector2
  .long vector3
;...
;==========skipped=========
;...
  .long vector254
  .long vector255
Таким образом, при нажатии на кнопку клавиатуры, вызывается соответствующий обработчик прерывания vectorN, который помещает в стек свой номер и вызывает функцию alltraps из файла trapasm.S. Данная функция вызывает уже сишную функцию обработки прерываний из файла trap.c - trap(struct trapframe * tf).
Ну а в данной функции, по номеру прерывания, переданному в структуре tf, мы узнаем, что получили прерывание от клавиатуры и вызываем функцию kbdintr() из файла kbd.c, занимающуюся чтением ввода пользователя.
case T_IRQ0 + IRQ_KBD:
    kbdintr();
    lapiceoi();
    break;
Точнее, это делает не сама функция kbdintr(), а вызываемая ей функция consoleintr() из файла console.c:
void
consoleintr(int (*getc)(void))
{
  int c;

  acquire(&input.lock);
  while((c = getc()) >= 0){
    switch(c){
    case C('P'):  // Process listing.
      procdump();
      break;
    case C('U'):  // Kill line.
      while(input.e != input.w &&
            input.buf[(input.e-1) % INPUT_BUF] != '\n'){
        input.e--;
        consputc(BACKSPACE);
      }
      break;
    case C('H'): case '\x7f':  // Backspace
      if(input.e != input.w){
        input.e--;
        consputc(BACKSPACE);
      }
      break;
    default:
      if(c != 0 && input.e-input.r < INPUT_BUF){
        c = (c == '\r') ? '\n' : c;
        input.buf[input.e++ % INPUT_BUF] = c;
        consputc(c);
        if(c == '\n' || c == C('D') || input.e == input.r+INPUT_BUF){
          input.w = input.e;
          wakeup(&input.r);
        }
      }
      break;
    }
  }
  release(&input.lock);
}
Видно, что введенная строка записывается в буфер input, объявленный чуть выше.
#define INPUT_BUF 128
struct {
  struct spinlock lock;
  char buf[INPUT_BUF];
  uint r;  // Read index
  uint w;  // Write index
  uint e;  // Edit index
} input;

Дальше в дело вступает наша командная оболочка, которая сначала читает строку, введенную пользователем. Делается это функцией gets() из стандартной библиотеки C, используемой в xv6 - ulib (файл ulib.c). В свою очередь, функция gets() использует системный вызов read(). Ну а дальше, все как обычно - приходит прерывание, отлавливаемое в функции trap() (файл trap.c) и вызывается функция syscall() из syscall.c. При этом в регистре eax, в контексте процесса, вызвавшего системный вызов, остается номер этого вызова. По нему ядро и принимает решение использовать соответствующую функцию - sys_read() в нашем случае.
int
sys_read(void)
{
  struct file *f;
  int n;
  char *p;

  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0)
    return -1;
  return fileread(f, p, n);
}
Функция fileread() из файла file.c определяет, что мы пытаемся читать из файла - sh читает ввод пользователя со стандартного ввода (STDIN), что есть файл - и перенаправляет нас к функции readi() из fs.c. В этой функции мы используем функцию read() (не системный вызов read()!!), выбранную в соответствии с номером устройства из структуры devsw.
if(ip->type == T_DEV){
    if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)
      return -1;
    return devsw[ip->major].read(ip, dst, n);
  }
Эта массив структур объявлен в file.h как:
struct devsw {
  int (*read)(struct inode*, char*, int);
  int (*write)(struct inode*, char*, int);
};

extern struct devsw devsw[];
...и проинициализирован для стандартного ввода внутри файла console.c как:
devsw[CONSOLE].write = consolewrite;
devsw[CONSOLE].read = consoleread;
Таким образом, при вызове функции read() для символьного устройства стандартного ввода, вызывается функция consoleread(), которая копирует прочитанные данные из буфера input в область памяти, указанную системному вызову read().
В итоге, введенные пользователем символы "ls", после длинного путешествия через системные функции, оказываются в распоряжении нашего командного интерпретатора, который парсит их и запускает на выполнение, предварительно форкнувшись. Для запуска (как ни удивительно!) используется системный вызов exec().
int
sys_exec(void)
{
  char *path, *argv[20];
  int i;
  uint uargv, uarg;

  if(argstr(0, &path) < 0 || argint(1, (int*)&uargv) < 0) {
    return -1;
  }
  memset(argv, 0, sizeof(argv));
  for(i=0;; i++){
    if(i >= NELEM(argv))
      return -1;
    if(fetchint(proc, uargv+4*i, (int*)&uarg) < 0)
      return -1;
    if(uarg == 0){
      argv[i] = 0;
      break;
    }
    if(fetchstr(proc, uarg, &argv[i]) < 0)
      return -1;
  }
  return exec(path, argv);
}
Непосредственно запуском программы занимается системная функция (не системный вызов!!) exec() из файла exec.c. Она копирует машинный код утилиты ls с диска в память, инициализирует для нее стек, настраивает структуру proc с описанием процесса ls. Дальше, работа утилиты зависит от планировщика и от собственного поведения...

Ссылки

Страница xv6
Страница курса 6.828 в MIT

4 комментария:

  1. А у меня выдает:

    gcc -o mkfs mkfs.c

    /usr/bin/i586-alt-linux-gcc: No such file or directory

    make: *** [mkfs] Ошибка 1

    Хотя все на месте. К сожалению, не программист так что разобраться сложно. Всякие -Wall я сам уже убрал.

    ОтветитьУдалить
  2. Так у вас же gcc не установлен! Вот система и пишет, что "gcc: No such file or directory"

    ОтветитьУдалить
  3. Блин, точно! Спасибо! Но он же был установлен у меня здесь на Alt'e - я где-то год назад пробовал Hello world и простенькие программы писать и компилить в командной строке, причем и для С и для C++, а сейчас и g++ тоже нет. Как же компилятор мог исчезнуть, систему я не сносил она у меня уже пару лет нормально работает. Но сейчас все заработало и xv6 запустилась, так что еще раз благодарю!!

    ОтветитьУдалить