Что-то с памятью моей стало...

Не люблю ограничения, ни в чем, особенно если эти ограничения ничем не оправданны. От оправданных ограничений никуда не денешься, и ничего с ними не поделаешь.

Мое ядро загружается с помощью GrUB, который не умеет загружать ядро или модули ниже мегабайта. И это накладывает на меня ограничение - одного мегабайта памяти просто не хватит GrUB'у. Но двух мегабайт должно хватать и мне и ему.

Но неладно что-то в датском королевстве...

Попытавшись поставить 2 мегабайта для bochs я услышал от GRUB следущее:

GNU GRUB version 0.96 (639K lower / 4193279K upper memory)

Хех, очень забавно... То же самое я увидел запустив qemu... И что самое интересное, что то же самое GRUB докладывает моему ядру.

Попробуем поднять планку до 4 мег.

GNU GRUB version 0.96 (639K lower / 1984K upper memory)

bochs и qemu вновь единодушны, но где еще один мегабайт??? Ведь по логике вещей должно быть 3М upper...

8M: GNU GRUB version 0.96 (639K lower / 6080K upper memory)
16M: GNU GRUB version 0.96 (639K lower / 14272K upper memory)

Нет, надо с этим что-то делать...

PS: Одно место обнаружилось в bochs bios, он от размера памяти отнимает ACPI_DATA_SIZE, но это не может послужить причиной пропажи целого мегабайта, ACPI_DATA_SIZE имеет значение 64к.

PPS: Эх, чуть чуть недотестировал...

17M: GNU GRUB version 0.96 (639K lower / 16320K upper memory)!

Ошибка скрывалась в Биосе bochs в функции 0xe820, int 0x15. Если памяти больше 16 мегабайт, то анализируется количество 64-х килобайтных блоков после 16 мегабайт, 16 мегабайт прибавляем. А если памяти ровно или меньше 16 мегабайт, то анализируется количество килобайтных блоков после мегабайта... А вот мегабайт прибавить забыли.

QEMU использует биос из комплекта bochs, поэтому проблема присутствует и там.

Разворот стека методом трассировки кода (описание)

Предпринял попытку описать разворот стека методом трассировки кода, заодно проверил функционирование wiki на Google code. Они конечно хитрые, хранят wiki документы непосредственно в subversion репозитории. Портят мне логи, хотя по большому счету это разумный ход.

Это кстати новость. Перенес проект под Google code. Ну Subversion - он и в Африке Subversion, а вот Downloads сделан гораздо лучше. Да и wiki - это плюс. Что еще нужно от проектного хостинга по большому счету...

О практической пользе константных параметров...

Практики хорошего программирования рекоммендуют никогда не менять параметры функций в теле. Но чрезмерное применение const так загромождает прототип функции, не хочется, но альтернативы этому нету. const'ом метод не испортишь :) и параметр, как показывает практика - тоже.

Не далее как вчера описывал точки входов системных вызовов в ядро. Логика ассемблерной прослойки проста - сохранить все кроме eax, вызвать высокоуровневый метод-обработчик и корректно же выйти. Но это выливается примерно в такой код:

KernelWait:
       pushfl
       pushl %ebx
       pushl %ecx
       pushl %edx
       pushl %esi
       pushl %edi
       pushl %ebp

       pushl %ds
       pushl %es
       movl $KERNEL_DATA_SELECTOR, %ebx
       movw %bx, %ds
       movw %bx, %es

       pushl %edx
       pushl %ecx
       pushl %ebx
       pushl %eax
       call StubWait
       add $16, %esp

       popl %ds
       popl %es

       popl %ebp
       popl %edi
       popl %esi
       popl %edx
       popl %ecx
       popl %ebx
       popfl

       iret

Глядя на эту функцию часть кода может показаться лишней. Вполне логично было бы написать так:

KernelWait:
        ...
       pushl %edx
       pushl %ecx
       pushl %ebx
       pushl %eax
       call StubWait
       add $4, %esp
       popl %edx
       popl %ecx
       popl %ebx
        ...
       iret

Но если сделать так, то любое изменение параметра функции в ее теле повлечет за собой изменение регистра приложения, который мы не должны менять.

int StubWait (int a, int b, int c, int d) 
{
       d += 10;

Очень плохо! Разумным способом предотвращения данной ситуации является описание всех параметров константными.

int StubWait (const int a, const int b, const int c, const int d) 
{
        int dnew = d + 10;

Так значительно лучше и не грозит проблемами. Кроме того думаю, что привычка объявлять все методы функций константными даст компилятору больший простор для оптимизации. Это предположение, но компиляторы сейчас умные, обявление константости в следующем случае:

static const
struct console StubXGAConsole = {
       .putc = StubXGAPutC,
       .getc = StubXGAGetC,
};

static const
struct console *sConsole = &StubXGAConsole;

позволило компилятору, при отсутствии явной модификации sConsole, вообще атрофировать эту переменную, не смотря на то, что сам по себе sConsole модифицируемый.

PS: А экономия на push/pop очень напоминает преждевременную оптимизацию, к тому же нелогично после вызова функции пупать параметры обратно, поэтому лучше я воздержусь от такого вида оптимизации. Тем более что я использую единственный макрос для всех 8 системных вызовов.

Тайна двух конструкторов...

Опять обнаружил странное дело. Начал вносить в свое ядро c++ код, и сразу же новая загадка...

Надо сказать, что я не очень люблю загадки. Я предпочитаю иметь полный контроль над кодом. И когда происходит что-то, чего я не понимаю, я начинаю нервничать, проклинать тот день, когда я решил переписать ядро частично на c++, и вообще...

class RandomGenerator {
public:
 RandomGenerator ();
        ...
};

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

001039ac T RandomGenerator::RandomGenerator()
001039cc T RandomGenerator::RandomGenerator()

Начинаем выяснять почему...

$ nm Kernel-IA32
...
001039ac T _ZN15RandomGeneratorC1Ev
001039cc T _ZN15RandomGeneratorC2Ev

Наверное в двух экземплярах конструктора есть какой-то глубокий смысл. Но если обратить внимание на то, что они оба располагаются в одной секции, странно это. Я мог бы понять расположение двух одинаковых конструкторов в разных секциях, инициализация там, всякое такое, мог бы понять если бы у них было разное тело... Ан нет.

$ objdump -d Kernel-IA32
Disassembly of section .text:

001039ac <_ZN15RandomGeneratorC1Ev>:
  1039ac:       53                      push   %ebx
  1039ad:       83 ec 10                sub    $0x10,%esp
  1039b0:       8b 5c 24 18             mov    0x18(%esp),%ebx
  1039b4:       68 71 15 00 00          push   $0x1571
  1039b9:       53                      push   %ebx
  1039ba:       e8 6f fe ff ff          call   10382e <_ZN15RandomGenerator4initEm>
  1039bf:       89 5c 24 20             mov    %ebx,0x20(%esp)
  1039c3:       83 c4 18                add    $0x18,%esp
  1039c6:       5b                      pop    %ebx
  1039c7:       e9 70 fd ff ff          jmp    10373c <_ZN15RandomGenerator6reloadEv>

001039cc <_ZN15RandomGeneratorC2Ev>:
  1039cc:       53                      push   %ebx
  1039cd:       83 ec 10                sub    $0x10,%esp
  1039d0:       8b 5c 24 18             mov    0x18(%esp),%ebx
  1039d4:       68 71 15 00 00          push   $0x1571
  1039d9:       53                      push   %ebx
  1039da:       e8 4f fe ff ff          call   10382e <_ZN15RandomGenerator4initEm>
  1039df:       89 5c 24 20             mov    %ebx,0x20(%esp)
  1039e3:       83 c4 18                add    $0x18,%esp
  1039e6:       5b                      pop    %ebx
  1039e7:       e9 50 fd ff ff          jmp    10373c <_ZN15RandomGenerator6reloadEv>

Они полностью идентичны за исключением смещений. Загадка однако. Стоит отметить, что других конструкторов тоже два.

0010388c T RandomGenerator::RandomGenerator(unsigned long const*, unsigned long)
001039ec T RandomGenerator::RandomGenerator(unsigned long const*, unsigned long)

Как с этим бороться?

Разворот стека методом прямой трассировки кода.

Во, как загнул... и это не шутка, метод уже реально работает.

RISC - это наверное рай для программистов на ассемблере. И для программистов компиляторов заодно. Это же счастье, когда любая инструкция занимает ровно 32 бита, и общее количество инструкций порядка 3 дестков...

Но нет, мы на земле. Количество инструкций IA32 не поддается трезвому подсчету. Но мы всетаки пишем и не компилятор, нам достаточно лишь достоверно выяснить, какая функция какую вызывает, на основании имеющегося под рукой стека.

И вот, намедне, мне пришла в голову идея, что разворачиват стек можно не только с хвоста, но и с головы. Идея пришла посте того, как после перехода в страничный режим заглючила старая версия разворота стека. Её конечно можно было бы поправить, но новая идея захватила меня целиком, и не отпускала почти три дня.

Для разворота стека методом прямой трассировки кода - необходимо для начала определить какую либо точку кода. Чтобы проделать это - мы берем первое слово из стека, причем, это именно голова стека, то есть то место откуда стек начался. И проверяем, не может ли это значение быть адресом возврата? Для этого необходимо убедиться, что перед ним стоит инструкция вызова.

Можно сказать что это режим разворота без точки выполнения. Мы еще будем к нему возвращаться в случае потери адреса.

    инструкция call (в любой форме)
value <-- адрес возврата

Стоит отметить, что в новой версии я везде проверяю доступность памяти. Первая версия разворачивателя вполне могла бы вызвать PageFault.

В случае обнаружения адреса инструкций - включаем режим трассировки. Трассировка осуществляется до тех пор, пока указатель трассировки не совпадет с адресом, на котором прервалось выполнение приложения. Если встречается какая-либо инструкция, явно показывающая, что код не соответствует стеку, то данный вариант разворота отменяется, трассировка пошла в неправильную ветвь.

Кого-то, может быть, пугает слово трассировка, но не стоит пугаться. Нам вовсе не обязательно эмулировать все инструкции. Мы анализируем следующие группы инструкций:
Инструкции, модифицирующие содержимое регистра esp, двигают указатель стека; Инструкции безусловных переходов передвигают указатель трассировки, за исключением случая, когда переход осуществляется на саму инструкцию; Инструкции условных переходов проверяются по обоим ветвям. Что касается различных форм инструкции call - то адрес в стеке обязательно должен соответствовать адресу следующей инструкции, иначе этот call протрассировывается мимо. По разумным соображениям я не включаю в список команд вызова различные прерывания. Да и не все call'ы одинаково полезны, как я уже писал раньше. Я могу точно определять явно заданные адреса, но косвенные формы лишь показывают что вызов есть, но куда было передано управление - остается неизвестным, происходит потеря адреса.

Анализируется еще одна ситуация, когда содержимое стека соответствует срабатыванию исключения (адрес возврата, селектор сегмента), но в этом случае происходит потеря адреса, ибо доподлинно не известно, какое исключение сработало.

Остальные инструкции достаточно просто пропустить, но тут то нас поджидает один неприятный момент, на IA32 инструкции имеют очень переменную длину, и определение длины текущей инструкции - задача весьма нетривиальная. Мне удалось решить ее с помощью двух таблиц, по 256 байт каждая, и небольшой функции. Но таблицы я еще не заполнил до конца.

В этом методе осталось еще не реализованной возможность определения количества аргументов, но теоретически это возможно.

Пока что, без переходов через шлюзы - результат вполне обнадеживающий:

CallStack: Stopped in StubKernelUsePage+122 (0x00102a00)
CallStack: Called by StubPageInitMode+31 (0x00100df9)
CallStack: Called by StubEntry+587 (0x00101428)
CallStack: Called by unknown+0 (0x001000d4)

Последняя точка осталась неизвестной, потому, что для определения символа необходимо отмотать по коду несколько команд назад StubEntryLo=0x001000cc, но это мелочи по большому счету.

.bss в файле???

Всем известно, что .bss это неинициализированная секция и не должна занимать места в файле, но собирая на досуге свое ядро наткнулся на проблему. .bss почему-то находится в файле и занимает там много места, хотя не должна.

Ага, понятно, все происходит из за стека, который я хочу включить в .bss, но именую словом .stack.

Не знаю, почему в binutils или в gcc или где там, уж не знаю, придают такое значение именам, но
3 .stack 00001000 00000000 00000000 00000298 2**0
CONTENTS, READONLY
В то время как переименованная секция
3 .bss.stack 00001000 00000000 00000000 00000298 2**0
ALLOC

Теперь стало гораздо лучше.

PS: У меня почему-то комплекс, боязнь толстых программ. А еще у меня есть старое ядро, которое полностью занимало 17KiB, оно у меня как некий образец объема. Новое конечно будет больше, но пока стрипнутое занимает 15KiB.

В любом случае, комплекс - не комплекс, но 5 килобайт нулей - это слишком расточительно.

Что первичнее - cтраницы или сегменты?

Ну лаконичность .S длилась недолго... Сейчас в нем начинает прибавляться функций, переходники для исключений, большинство реализуется через единственный макрос. Этот макрос подойдет так же для переходников прерываний, но не подойдет для сервисов. С ними вообще сложнее, для каждого системного вызова понадобиться свой переходник.

И еще никак не удается исбавится от зависимостей. В переходниках необходимо явно использовать селектор данных ядра, но поскольку сишный дефайн там не доступен - приходится мучаться. Либо определить константу в .S (она превратиться в метку sic! да и одна константа описанная дважды - плохо), либо писать явное значение (хардкод еще хуже чем сдублированая константа), или можно заложиться на взаимозависимость cs и селектора кода данных (ds = cs + 8) (не слишком ли хитро все запутано?). Наиболее предпочтительным выглядит первый вариант, если бы он не превращался в метку, а так второй вариант с комментарием наверное не слишком плохо (пока один раз, но одним разом не обойдется, придется дефайнить).

В этом ядре я пошел на небольшую хитрость... Архитектура IA32 устроена так, что сегментная защита реализуется на уровне линейной памяти (то есть страничное преобразование - это более низменный механизм). Это, по логике вещей, требует инициализировать сперва страничное преобразование, а уж потом включать сегменты и таблицы прерываний. Но таблица прерываний, а в частности исключения, весьма полезная штука. Чем раньше они будут включены, тем лучше. Поэтому я сперва проинициализировал GDT и IDT. Но поскольку адреса таблиц при переходе в страничный режим не изменятся, то и значения это не имеет.

Это в старое ядро я мог по началу мапить куда угодно... Это было конечно очень круто, но по большому счету бесполезно. Гораздо проще оказалось мапить ядро по тем же адресам, по которым оно загружено, что и было сделано еще в прошлой версии ядра. Но порядок инициализации страницы, сегменты сохранился... А теперь, когда я исходно не собираюсь менять адреса, то могу позволить себе такие вот маленькие хитрости.

GNU as

Почему-то последнее время у меня сформировалось ошибочное мнение, что препроцессор as аналогичен сишному, что позволяет пользоваться одними заголовками на всех, и вообще очень удобно... Но как же я ошибался...

До сих пор я не особо писал на as. Так, инлайны иногда... но вот в последнем ядре решил переписать минимальную ассемблерную часть на as, ибо она настолько минимальна, что нет смысла ради нее держать еще один дополнительный инструмент вроде nasm/yasm.

Но как выяснилось as препроцессор нисколько не совместим с си. А применение сишного препроцессора к .s файлам может привести к загадочным результатам... Например ключевое слово .arch i386 после си препроцессинга превращается в... .arch 1 :(. А константа, описанная в ассемблерной нотации автоматически становится абсолютной меткой. Интель синтакс вообще не понятно как использовать.

Но есть и положительные моменты... Например все неописанные имена автоматически становятся внешними.

Короче после некоторых экспериментов мультибут заголовок был перенесен в сишную часть, а в ассемблерной части остались лишь минимальные функции, которые пока не нуждаются в каких либо константах... зато лаконичности прибавилось. Ассемблерная часть получилась весьма прозрачная.

Переключение задач.

Тема, по которой не прекращаются споры сторонников различных подходов.

Но вот недавно SadKo предложил интересную идею, которой я не премину воспользоваться (Если, конечно, SadKo не будет сильно возражать и настаивать на своем исключительном авторском праве :)).

Идея в принципе не нова, и заключается в том, что переключениями задач занимается отдельная задача, что, собственно, упрощает процесс менеджмента. При этом я, скорее всего, не стану полностью переводить весь ядерный API в отдельные задачи, это не оптимальный и не самый удобный способ реализации, ИМХО. Более того, даже прерывание таймера не достойно того, чтобы выносить его в отдельную задачу. Тем более, что прерывание таймера вовсе не подразумевает переключения задачи, в том смысле что переключение может и не понадобиться.

Менеджер задач будет отдельной задачей, но не будет напрямую доступен приложениям, а будет вызываться самим ядром при необходимости такого переключения.

Конечно, это будет приводить к дополнительным расходам времени (одно дополнительное переключение задачи). Да ну и пусть. Зато удобно. В старой реализации мне приходилось постоянно ломать голову над тем, как проделать над задачей какие либо манипуляции, учитывая, что она еще не покинула процессор. И приходится мучиться.

PS: И еще подумал, что на многоядерной системе вероятно потребуется сделать несколько задач - переключателей (по одной на каждый процессор), или одну задачу но с блокировкой (этот вариант наверное попроще).

Использование памяти...

А тем временем я, наконец то, создал временный хип и уже разместил в нем символы ядра...

С размером временного хипа не все однозначно.
С одной стороны размер памяти известен, и легко можно предсказать сколько памяти потребуется для хранения внутренних таблиц страниц (не путать с таблицами IA32). Так же легко можно предсказать - сколько памяти потребуется для дескрипторных таблиц IA32, потому что их размер фиксированный. Остается только память, необходимая для инициализации модулей и для хранения символов. Модулям много не надо, тем более что они не активизированные, но необходимо учитывать их количество (временно положил по килобайту на модуль).

А вот размер таблицы символов может быть определен только в процессе разбора. Ну я думаю что несколько килобайт временного хипа про запас проблемы не составят. Тем более что я уменьшил размер PageInfo в два раза по сравнению в предыдущей версией.

Еще я придумал как правильно каскадировать регионы. Я буду делать это через инстанции, что позволит пользоваться механизмом инстанций для высвобождения родительских регионов, и не изобретать еще один велосипед.

А еще пришла в голову интересная мысль, что модули, загружаемые GrUB могут быть вытеснены в своп средствами лоадера, ибо путь к модулям мы знаем! Естественно не все модули могут быть высвоплены. Непосредственные участники процесса должны всегда находиться в памяти (может быть специальный флажек в процессе предусмотреть? всеравно своппингом будет управлять ядро).

Костыли и не очень...

Вот думаю, почему так странно сделана загрузка с USB в современных биосах? очень похоже на костыль...

Вытаскиваешь флешку - он тот час же забывает, что диск был выбран... Ну всмысле тот час же после перезагрузки :). Вставляешь, надо пойти в Boot/Hard devices (точно не помню) и установить там в первую очередь флешку... Но все исчезнет с вытаскиванием флешки (тот час же после перезагрузки опять таки).

Не проще ли было в списке устройств рядом c 1-st Floppy установить и USB Drive. Всетаки это removable устройство. При отсутствии с флешки он просто грузился бы с очередного устройства. Думаю было бы логично.

А теперь немного мыслей о системе.

А еще после написания предыдущего поста я подумал, что я пожалуй все буду выделять динамически... В том смысле, что даже дескрипторные таблицы. Очень удобно ИМХО будет. Тем более, что GDT мне нужна весьма порядочная. Поскольку дескрипторы TSS я устанавливаю динамически, то пусть для них будет больше места в таблицe. Думаю, заведу GDT записей на 1000. Малое количество записей в GDT старого ядра вынуждает постоянно переставлять дескрипторы TSS, что не может не сказаться на производительности. Но с другой стороны раздувать GDT на максимальный размер - тоже не имеет смысла. Кому нужны одновременно 8000 нитей?

А еще пришла интересная мысль только что... Можно непосредственно рядом с дескриптором TSS хранить ссылку на его структуру. Просто пометить соседний дескриптор как отсутствующий, но от этого не менее содержательный.

Хотя подумал еще немного и понял, что большого смысла в этом нету. Я и через указатель на TSS спокойно могу достать все необходимые структуры...

Поглощение памяти...

Есть много различных алгоритмов динамического распределения памяти. Я для себя выбрал один в меру быстрый, но не буду сейчас углубляться в его тонкости. Сейчас я хотел рассказать об одной хитрости, которая позволит не создавать статически выделенную память до перехода в страничный режим.

Любая динамически выделяемая память выделяется блоками. И обычно у каждого блока есть заголовок.. но прежде, чем создать рабочий хип ядра нам необходимо провести ревизию системных ресурсов, и создать списки страниц... То есть память нам нужна еще до того, как ядро войдет в рабочий режим и обзаведется полновесным хипом. Но как это сделать?

Списки страниц могут занимать разное количество памяти. Это зависит от количества собственно памяти в системе. Необходимо создать временный хип, который сможет вместить в себя списки страниц и некоторую другую информацию, определяемую до перехода в страничный режим. Количество памяти нам любезно предоставляет GrUB.
И мы получаем размер, который для удобства округлим до страниц.

Выбирая место для временного хипа необходимо подумать о том, чтобы он целиком размещался в линейном пространстве рабочего хипа, иначе хитрость не получится.
А рабочий хип располагается от конца ядра до начала области пользователя (до сих пор эта граница проходила на 128 мегабайтах). Но нам мешают модули, которые лежат в физической памяти после ядра. Проанализировав списки модулей, мы определяем начало свободной памяти.

Осталось только проконтролировать, что оставшегося количества физической памяти хватит на размещение временного хипа. В нынешние времена это конечно не проблема, но если вдруг памяти окажется по настоящему мало (2 мебибайта к примеру) эта проблема может встать остро.

Но вот место и размер для временного хипа определены, инициализируем его и начинаем резать на блоки. Места должно хватить на все.

Для успешного перехода в страничный режим мы должны замапить ядро и собственно временный хип. Маппинг осуществляется один к одному. То есть, в страничном режиме все указатели на хип останутся актуальны по-прежнему. Но теперь нам нужно организовывать рабочий хип. Делается это не совсем линейно, мы определяем в свободные блоки линейную память до временного хипа и после него. Блоки временного хипа получают новые привязки к рабочему хипу. По необходимости дефрагментируются, и временный хип перестает существовать, будучи поглощенным рабочим. При этом, опять таки, все указатели со времени инициализации сохраняют свою актуальность.

Вот собственно такие планы на хип нового ядра. На этом на сегодня все.

Разворот стека (приквел)

Я понял почему прошлая статья получилась сбивчивая. Потому, что я не рассказал, для чего все это надо и с чего собственно все начинается! Сейчас исправлюсь.

Для облегчения диагностики ошибок в ядре издавна применяется такое средство, как синий экран смерти. Ну все прекрасно знают что и зачем он содержит... (видели неоднократно). Но стоит заметить, что сухие столбики цифр не всегда доходчивы даже для разработчика. В новом ядре я попытаюсь исправить эту ситуацию. То есть постараюсь сделать BSoD максимально наглядным и информативным. Пусть даже его кроме меня никто никогда не увидит :) Зато меня он будет радовать каждою иголочкой. :)

Из нововведений нового экрана смерти можно отметить содержательное сообщение об ошибке, с указанием файла и строки где все это, собственно, произошло. Потом немаловажной является возможность посмотреть на содержимое экрана в момент сбоя. И последним является развернутый стек. С технологией чего собственно и делюсь.

Так вот, ситуация на момент сбоя складывается такая, что мы имеем указатель на некоторую инструкцию (что это за функция - нам неведомо). Кроме этого мы имеем указатель на вершину стека. Почему ее назвали вершиной - история умалчивает, все знают что стек растет вниз, это объясняется в частности тяготением земли, но тем не менее вершина стека называется вершиной хотя на самом деле все с точностью до наоборот, но к делу это не имеет отношения.

И вот не зная почти ничего нам необходимо определить что же это за функция такая, сколько у нее локальных параметров, сколько аргументов и кто ее собственно вызвал. И чтобы все это узнать - мы начинаем подниматься по стеку вверх. Значения, явно не похожие на адреса мы отбрасываем не глядя. Похожие на адреса значения мы анализируем. И анализируем мы их примерно так: Берем вот это похожее на адрес значение. и смотрим, что находится в памяти в этой области. Если за пять байт до указанного места находится байт 0xe8, то, возможно мы на верном пути. Проверяем смещение, которое должно указывать на адрес обязательно до текущей инструкции, если это так, то можно предположить что мы на верном пути. записываем функцию номер 1 и двигаемся дальше.

Дальше, в качестве текущего указателя берем адрес указывающий на тот call, который мы распознали (за пять байт до предыдущего адреса возврата). И начинаем сканировать стек дальше. Получаем вторую, третью и тд функции...

После достижения дна стека (четкой границы у стека нету, я для себя предполагаю, что стек заканчивается на границе страницы) мы имеем список функций. некоторый из которых могут оказаться ложными. И вот мы начинаем с самой первой функции проверять их на взаимовызовы. Если проверка взаимовызовом не проходит - функция помечается как неуточненная. И на данный момент такие функции не отображаются в стеке вызовов.

На данный момент все неуточненные функции действительно левые. Но с началом использования C++ ситуация наверное усложнится. Потому что виртуальные функции на 100% вызываются косвенно. Придется усложнять алгоритмы. Красота требует жертв.

Разворот стека

Я в репозитории уже писал 101 способ разворота стека (шучу конечно). Но на практике все оказалось, конечно, сложнее.

Но одно можно сказать точно - в стеке всегда храниться адрес возврата на функцию верхнего уровня, который указывает на инструкцию, следующую после call.

IA32 насчитывает порядка 33 варианта внутрисегментных вызовов функций. 32 из которых хранят адреса в регистрах или в памяти, докопаться до этих адресов при развороте стека нереально (закон жизни?). Но есть одна форма, использующаяся в большинстве случаев, при которой не просто реально, а тривиально (закон Фостерс!).

Эта форма выглядит так: call rel32
rel32 задает смещение относительно адреса следующей команды, который лежит у нас в стеке как адрес возврата. То есть эта форма позволяет одним легким движением найти адрес функции которая была вызвана.

foo();                       bar();

Стек:                            ...
   ...                          call foo     ; e8 (foo - <адрес возврата>)
   адрес возврата          ---> ...
   ...

При обнаружении остальных форм команды call мы не можем точно определить адрес начала функции, но, мы знаем хотя бы, что этот адрес в стеке на самом деле является адресом возврата а не мусором, а это уже что-то.

Но не все гладко. В зависимости от режима оптимизации да и сам по себе стек может содержать адреса, которые на самом деле не относятся к текущей иерархии вызовов а остались в стеке с былых времен.

foo();                       tar();

Стек:                           ...
   ...                          call moo     ; e8 (moo - <адрес возврата>)
   адрес возврата          ---> ...
   ...                          ret

                             bar();
                                ...
   ...                          call foo     ; e8 (foo - <адрес возврата>)
   адрес возврата          ---> ...
   ...

При сканировании стека мы сперва обнаруживаем ссылку на tar, который на самом деле не вызывает foo! Такая ссылка может возникнуть при резервировании пространства для локальных переменных foo.

Я пока не придумал ничего лучше, чем сканирование функций на тему соответствия вызовов адресам. Если в стеке обнаружится адрес возврата, указывающий на функцию, в теле которой обнаруживается вызов текущей функции - это однозначно говорит о том, что эта функция относится к текущей иерархии вызовов. В то время как отрицательный результат вовсе не означает того, что функция не из этой иерархии (см выше про 33 формы оператора call), а просто заставляет относится к ней с подозрением. Реальную причастность к иерархии вызовов можно подтвердить и другими способами.

Но об этом пожалуй в другой раз.

PS: Сбивчивая получилась статья, особенно со слайдами. :(

Процентики

Долго думал как лучше обработать вывод чисел, результатом чего до недавного времени были функции вывода целых чисел, шестнадцатеричных ну и других, которые требуются.
Не знаю что послужило толчком - но вдруг я осознал, что независимо от основания числа все они могут использовать одну таблицу символов для отображения.

Наверное слишком тривиальная мысль. Но это позволяет обходиться одной функцией для вывода чисел любого основания.

Ради интереса заглянул в glibс... Ох, зря я это сделал... функция vfprintf у них начинается с 985 строк, который представляют из себя макросы препроцессора... Затрудняюсь сказать что они вызывают для вывода чисел.

Интерес еще не кончился и я загляенул в uСlibc - и тоже сходу не смог докопаться до истины.

Но вот в dietlibc все более доходчиво... они тоже грамотно используют одну функцию только предпочитают не рекурсию а цикл.

Но мне немного проще, мне не требуется поддержки знаков, ограничение ширины вывода, разный кейс символов. Моя функция вывода символов имеет только ограничение минимальной длины и использует рекурсию.

static
void StubPrintNum (unsigned long n, int base, int minlen)
{
   assert (base > 0 && base <= 16);      if (minlen > 1 || n >= base)
       StubPrintNum (n / base, base, minlen - 1);

   StubPrintChar ("0123456789ABCDEF"[n % base]);
}

И используется проще простого

case 'u':
 StubPrintNum ((unsigned long)*args++, 10, 1);
 break;

case 'x':
 StubPrintNum ((unsigned long)*args++, 16, 8);
 break;

Если минимальная длина окажется больше длины числа, то число будет дополнено нулями.
Соответственно нет никаких проблем для вывода двоичных, восьмеричных, даже radix50, если кому надо, только для этого придется расширить строку символов, или вводить условия.

Символизм ELF

Ну все оказалось вовсе не так страшно как предполагалось ранее. Секций строк действительно несколько, но они относятся к разным сущностям. GrUB передает нам номер секции, указанной в заголовке ELF, а эта секция содержит имена секций. нас она не интересует. Но нам нет никакой необходимости вообще смотреть на этот номер.

GrUB передает нам следующие поля заголовка ELF:

typedef struct {
   ...
   Elf32_Off     e_shoff;
   ...
   Elf32_Half    e_shentsize;
   Elf32_Half    e_shnum;
   Elf32_Half    e_shstrndx;
} Elf32_Ehdr;

e_shentsize нас интересует только ради успокоения души, чтобы сравнить его с размером нашей структуры.

e_shstrndx содержит номер секции строк с именами секций. Нас он не интересует в принципе, о чем я и писал выше.

Таблица секций состоит из структур Elf32_Shdr. Привожу только интересующие поля, чтобы не загромождать блог.

typedef struct {
    ...
    Elf32_Word sh_type;
    ...
    Elf32_Addr sh_addr;
    ...
    Elf32_Word sh_size;
    Elf32_Word sh_link;
    ...
    Elf32_Word sh_entsize;
} Elf32_Shdr;

Размер которой и должен соответствовать вышеуказанному полю e_shentsize. Наша задача состоит в том, чтобы найти секцию содержащую символы. Поле sh_type в этой секции будет иметь значение 2 (SHT_SYMTAB).

В этой секции содержатся записи типа Elf32_Sym, и естественно поле sh_entsize должно соответствовать размеру структуры. sh_size указывается в байтах, для преобразования в количество структур делим собственно на sh_entsize, остатка быть не дожно.

typedef struct {
    Elf32_Word    st_name;
    Elf32_Addr    st_value;
    ...
} Elf32_Sym;

st_value - это значние адреса. в некоторых случаях оно может быть нулевым, в частности для имен файлов, такие записи меня не интересуют, отбрасываем.

st_name содержит индекс (смещение) в секции символов. В некоторых случаях индекс может быть нулевым. при этом и ссылается он так же на нулевую строку, такие строки меня тоже не интересуют.

Но откуда же берутся строки?
Это очень просто. вернувшись к структуре Elf32_Shdr, мы заметим что там есть поле sh_link. Это поле служит для указания взаимосвязей между секциями и данном случе содержит индекс секции строк.

Секция строк представляет из себя массив asciiz (завершенных нулем) строк. Больше ничего не могу о ней сказать.

В результате мы имеем неупорядоченную таблицу символов.

Kernel (IA32) Stub-0.0.15.5 and UCore-
SYMTAB (sec#6) offset: 0x00102214, size: 448, link: 7
SYMTAB entry count: 28

0x00101000 .n_so
0x001000D6 Entry.Shutdown
0x0010111C StubPrintChar
0x001011D9 StubPrintInt
0x00101215 StubPrintHex
...

На данный момент отображаеся 16 символов. Но чтобы сохранить и упорядочить их нужен менеджер памяти, которого пока нету.

Я сейчас веду исследования по этому поводу, наверное опишу их чуть позже. В любом случае ядру еще предстоит переход в страничный режим. Думаю, что на время инициализации я заведу временный хип, который будет в состоянии вместить в себя всю накопленную информацию. А после перехода в страничный режим информация будет перемещена в основной хип.

Символизм GrUB...

Были мы молодыми, зелеными... не думали не о чем, кроме как о коде... написать побыстрее... посмотреть что получтся... И под конец зарыться окончательно. Проходит время и начинаешь понимать, что теряешься в том, что наворотил. Добавление новой фичи вообще становится нереальным. Слишком сложно...

Поэтому новое ядро, четвертое по счету, хотя третье если не считать второе :), начинаю писать с отладочных вещей.

Первым делом надо сделать экран смерти. Может быть для разнообразия сделать его зеленым :) ? А что самое главное в экране смерти? Смертельная красота Информативность!

Ну не буду пока говорить про регистры. От них всеравно никуда особо не денешься.
А вот стек - можно значительно приукрасить. Про точное определение параметров и локальных переменных функций я расскажу попозже, начинать надо с символов.

Это все была присказка... а теперь сказка!

Не вижу смысла обрабатывать a.out, хотя груб его может. Но для своего стаба я принял правило - платформа + формат бинарей это четко определено. И это правило позволяет отказаться от ненужного. Что касается ELF.

     If bit 5 in the ‘flags’ word is set, then the following fields in the Multiboot infor-
mation structure starting at byte 28 are valid:
               +-------------------+
    28         | num                   |
    32         | size                  |
    36         | addr                  |
    40         | shndx                 |
               +-------------------+
     These indicate where the section header table from an ELF kernel is, the size of each
entry, number of entries, and the string table used as the index of names. They correspond
to the ‘shdr_*’ entries (‘shdr_num’, etc.) in the Executable and Linkable Format (elf)
specification in the program header. All sections are loaded, and the physical address fields
of the elf section header then refer to where the sections are in memory (refer to the
i386 elf documentation for details as to how to read the section header(s)). Note that
‘shdr_num’ may be 0, indicating no symbols, even if bit 5 in the ‘flags’ word is set.

Было бы слишком наивным надеяться, что они предоставят всю информацию о символах ядра. Это всего лишь ссылка на таблицу секций ELF. Выбрать из них нужные - наша задача! Мы не можем ждать милостей от ELF!

Информаци я о символах в ELF хранится в двух секциях: секция таблицы символов и собственно секция строк. Ну структуры не буду приводить - ленюсь, Проблема только в том, что секций строк в моем ядре оказалось три... %-o

Kernel (IA32) Stub-0.0.14 and UCore-0.0.0
STRTAB offset is 0x00102169, size 12
STRTAB offset is 0x001021B9, size 57
SYMTAB offset is 0x001021F4, size 400
STRTAB offset is 0x00102385, size 159

Можно конечно предположить, что верна последняя, но думаю это должно как-то явно определяться. Буду думать. На этом прощаюсь.

Ссылки:
Multiboot Specification
ELF Specification (pdf)

Планирование работ 2

Очень даже неплохо, надо сказать, получается. Оформление пока страдает, но оформление пока не главное.

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

Группирующие работы не подразумевают приложения сил. На основании выполненности подработ можно вычислить степень выполненности работы. Как и листовые работы могут иметь статус завершенности. Логично выставлять этот статус после завершения всех подработ. Хотя на процентах выполнения это не скажется. Но с другой стороны 100% работы вовсе не означает что работа завершена, это всего лишь может означать, что на данный момент по данной работе все закончено.

Что касается рассчета процентов, то в моем случае все не настолько прямолинейно, как в Trac. Группирующая работа может состоять из 4 листовых работ разного уровня, при этом завершенность одной из работ даст всего 16% группирующей, и это не ошибка, поскольку группирующая состоит из 3 поработ, следовательно на каждую приходится по 33% прогресса. И одна из подработ первого уровня содержит еще две подработы, одна из которых будучи выполненой даст 50% на один уровень вверх, и 16% на два уровня вверх.

В принципе в развитии идеи можно будет добавить вес работы, который будет корректировать процентное соотношение подработ. Хотя эти проценты - не главное, это всего лишь фенечка.

Главное в идее - это возможность строить приоритетный список работ, в который входят незавершенные листовые работы, отсортированные на основе взаимоблокировок. В текущей реализации это пока выражено не полностью. Заблокированные работы если и должны входить в список TODO, то только с минимальным приоритетом и красным цветом.

Пока же результат выглядить примерно так:

Progress:
Stub-IA32-0.1:    0% [0/4].
Обработка символов ядра:          0% [0/3].
Синий экран смерти:       0% [0/1].

TODO list:
3 Получение информации о символах от GrUB
2 Получение информации о символах из секции ELF
1 Раздекорирование символов c++
0 Разворот стека
-1 UCore-0.1

Но для начала этого хватит. Если руки дойдут до графического интерфейса - то там можно будет добавить еще некоторые интересные фичи типа временнЫх отсечек и графиков, тех же весовых коэффициентов.

Планирование работ

Не для кого наверное не секрет, что системы управления коммерческими проектами не очень то подходят для бесплатного любительского софта. Это объясняется в частности тем, что коммерческий софт в основу угла ставит время и деньги, в то время как любительские разработки плевать хотели на все, кроме реального результата.

Вообще иногда мне кажется что люди для своих увлечений вообще ничего не планируют. Но вот лично я с некоторых пор начал испытывать такую необходимость, чем и сподвиг себя на поиски удобных приложений. Но тщетно. Может быть слишком многого хочу, но единственное более менее достойное решение, которое я знаю на сегодняшний момент - это trac.

Да только на мой вкус и trac не очень то хорош. Если немного подумать - то становится ясно, что milestone - это тоже работы, только более глобальные, нежели tickets. Но для меня остается не совсем понятным, почему не может быть и более мелких тикетов. Мне не хватает многоуровневости.

Идеальная система планирования, в моем представлении, выглядит так: организованная в виде дерева иерархия связанных взаимозависимостями работ. Это позволит начинать конкретизировать работы с этапа или идеи до конкретных атомарных действий, которые собственно имеют только два состояния 'готово' и 'не готово'. По состоянию конечных работ можно строит прогресс выполнения глобальных этапов. Взаимозависимости же нужны для того чтобы описывать взаимоблокировки между работами. При достаточном количестве взаимоблокировок станет возможным автоматически вычислять приоритетность работ, что может помочь в выборе направления усилий.

Это идея. Что же касается воплощения, то вебреализация замерзла в начальной стадии. Но сегодня, ковыряясь с taskjuggler, я вдруг понял одну очень простую истину. Чтобы хранить иерархию работ - не нужна база данных. Для этого вполне достаточно xml. Который останется всего лишь проанализировать для генерации необходимых репортов. Для чего, на первых порах, будет достаточно небольшой утилиты.

Чем я пожалуй в ближайшее время и займусь.

Материалы по теме:
Планирование программного обеспечения малой кровью, Джоэл Спольски.