понедельник, 24 сентября 2007 г.

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

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

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

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

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

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

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

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

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

пятница, 21 сентября 2007 г.

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

Я в репозитории уже писал 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: Сбивчивая получилась статья, особенно со слайдами. :(

четверг, 20 сентября 2007 г.

Процентики

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

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

Ради интереса заглянул в 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, если кому надо, только для этого придется расширить строку символов, или вводить условия.

среда, 19 сентября 2007 г.

Дети на дороге

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

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

Уволить дезигнера нафик! Ребенок должен стоять! Это позволит водителю до конца находиться в неведении относительно его картонной природы.

Даже тупые Американцы сделали лучше.

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

вторник, 18 сентября 2007 г.

Видимо-невидимо

Почитываю я иногда ITBlogs, весьма увлекательно... И вот статья навеяла странные мысли.

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

Но почему флеш на НЕВИДИМЫХ вкладках жрет ресурсы?
По логике вещей он должен стоять на паузе. Или вообще лежать в кеше, дожидаясь открытия вкладки.

А потом мы удивляемся почему компьютеры тормозят.

понедельник, 17 сентября 2007 г.

Планирование памяти

Тут вот недавно подумал, что древовидный динамический список работ во многом похож на карты памяти (mindmap). И не удивительно, что детальные работы облегчают понимание.

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

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

четверг, 13 сентября 2007 г.

Символизм 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 символов. Но чтобы сохранить и упорядочить их нужен менеджер памяти, которого пока нету.

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

вторник, 11 сентября 2007 г.

Символизм 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)

понедельник, 10 сентября 2007 г.

Планирование работ 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

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

четверг, 6 сентября 2007 г.

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

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

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

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

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

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

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

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