суббота, 29 декабря 2007 г.

Cryptoloop in action...

Что касается LPC2468 (ранее упоминавшегося ARM), то мне удалось отыскать hsc0 патч для ядра 2.6.11.8, что позволило отделить зерна от плевел... То есть отделить изменения касающиеся непосредствено плат LPC от изменений hsc0. Теперь я могу наверное с минимумом напильника наложить архитектуру LPC на более свежее ядро... Но это будет уже в следующем году.

А пока вожусь с шифрованием. Реализовал шифрование по ГОСТ 28147-89 для ядра, там оказалось все достаточно грамотно сделано в этом плане. Режимы работы блочных шифров (правда только CBC и ECB) ядро реализует универсально. От модуля шифрования лишь требуется предоставить две функции по шифрованию и расшифрованию блока. Мне даже удалось без проблем заставить работать со всем этим cryptoloop девайс. Шифрует эта железяка конечно очень медленно... ни один алгоритм не разогнался до 100kib/s, будем искать железку помощнее (пока положили глаз на Intel PXA 806Mhz).

Но не смотря на все трудности основной режим проекта - проходное шифрование флешек уже работает. То есть флешка втыкается к LPC2468 в хостовый разъем, а сама LPC2468 втыкается в комп как девайс. И комп видит флешку, как живую (только медленную), при этом если флешку просто воткнуть в комп, то видно, что над ней кто-то жестоко поиздевался, сплошной urandom.

Не знаю как они собираются сделать проходное шифрование IDE, SATA. Но задачка будет интересная.

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

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

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

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

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

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

GNU as

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

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

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

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

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

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

Контроль версий с svk...

Не знаю, кто как, но я без контроля версий вообще не могу.

Можно много спорить о том, какие из систем контроля версий лучше.
Но я последнее время пользуюсь SVK. Эта замечательная распределенная система контроля умеет зеркалировать cvs, subversion, perforce... Но даже если сервер зеркалируемой системы контроля недоступен, это не мешает вносить изменения в локальный репозиторий.

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

Но речь не о том... Недавно, с тех пор, как занялся с упоминаемым ранее армом) у меня возникла необходимость ковыряться в ядре, или того хуже - в uClinux... И вот тут то SVK меня подвел... чтобы загрузить в него проект такого размера (add, commit) нужно несколько часов (если не дней)... Хотя с незначительными изменениями в больших проектах он справляется без особых тормозов.

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

PS: К тому же всеравно, по работе может потребоваться сервер с системой контроля, чего svk не умеет в принципе - он по большей части frontend...

четверг, 13 декабря 2007 г.

Производители железа не умеют писать софт?

Бытует мнение... и думаю это действительно так. Щас докажу. :)

Работаю, как уже писал, с одной ARM'овой железякой от EmbeddedArtists. Ну начать наверное стоиит с того, что они положили в коробку с железякой...

В корорбке лежит CD, на котором записан exe файл, который представляет из себя 7z архив...

В архиве лежит образ vmware c устаановленным дебианом, в домашнем каталоге пользователя по умолчанию развернуты исходники uClinux, версии 20051014, уже пропатченные и настроенные на сборку. Справедлливости ради отмечу, что там все нормально собирается.

На сайте можно скачать патч, который, почему-то, не хочет накладываться на вышеозначенную версию uClinux. И который, помимо существенных изменений, касающейся данной борды, или хотя бы всех бордов данного производителя, содержит еще множество изменений в других подсистемах (преедпололжительно hsc патч и coldfire патч).

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

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

Но начатть стоит с того, что в крросскомпиляциях а уж тем более в ARM я не силен. Но и от своей любимой Gentoo отказываться не намерен. Берем crossdev и начинаем делать свои собственные toolchain. uclilbc почему-то вообщее не хочет собираться, может быть не любит ядро 2.6.23, инклюды от которого система ему подсовывает? arm-elf вполне успешно собрался (binutils, gcc-3, newlib), но с ним не захотел собираться busybox, который сказал примерно следующее:
/usr/libexec/gcc/arm-elf/ld: ERROR: /usr/lib/gcc/arm-elf/3.4.6/libgcc.a(_muldi3.o) uses hardware FP, whereas busybox uses software FP
Не совсем понимаю чем ему не нравится hardware FP. Ядро ведь должно его эмулирировать (поддержка включена), или на ARM'ах это не прокатывает?

Ладно, arm-softfloat-elf собрал все, да только очередной затык... все модули в системе получились elf, в то время, как ядро без MMU не может поддерживать ELF. :(

Начал разбираться а почему они собственно не Flat? дык очень просто. Для того, чтобы они стали flat, в binutils необходим дополнительный пакет - elf2flt, который через use флаги не активизируется, и на зеркалах нигде не лежит. Пришлось перековырять ebuild, благо кроссчейны лежат в оверлее... и наконец таки я собрал то, что они предоставили по умолчанию...
## Starting application at 0xA0008000 ...
Linux version 2.6.11.8-hsc0 (dron@mdf2007) (gcc version 3.4.6 (Gentoo 3.4.6-r2 p1.5, ssp-3.4.6-1.0, pie-8.7.10)) #5 Thu Dec 13 17:14:08 MSK 2007
CPU: Philips-lpc24xx [24000000] (ARMv3)
Machine: LPC24xx, NXP
...
init: Booting to single user mode
#
Кто-то скажет, что стоило ли столько мучится, тем более что в виртуальной машине все собирается... но мне в любом случае требовалось наладить свою сборку, мне в дальнейшем придется это менять, возможно дописывать модули.

вторник, 20 ноября 2007 г.

ARM

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

Новость первая заключается в том, что на работе меня подключили к новому проекту. Этот проект по созданию поточного шифратора USB. Делается это на базе контроллера с ARM'ом на борту. Я раньше никогда не имел дела с армами, хорошая возможность попробовать, тем более область использования армов весьма велика (портировать систему?).

Пока что балуемся с такой железякой. Компактная надо сказать железяка. процессорный модуль (представленный на изображении) имеет размеры 66х80мм при этом содержит 32 мега SDRAM, 128 мег (или правильно говорить меб?) флеша. Ну еще несколько флешей по мелочи (4 мега и 512 кил в чипе). Насколько я понимаю, вся эта память располагается в одном адресном пространстве, разница только в скорости доступа. Пока там крутится ucLinux, старый... не знаю что будет крутиться дальше, может свое что-то соберем. Там куча уникального оборудования, не поддерживаемого стандартным линуксом. Причем это только прототип, если прототип заработает, то будем делать другую железяку, конфигурация которой скорее всего будет отличаться от этой борды.

Но от столь интересного занятия меня безжалостно оторвали, говорят в старом проекте че-то не работает, сижу вот, туплю второй день... продукт тестируется, но я еще ни одного исправления не внес, ибо незачем. Отрицательно в проекте то, что мея привлекали в качестве экстренной помощи, и приходилось вдвоем ковыряться в одном проекте, больно он монолитный. 16 бит, msc++ 2.0, памяти постоянно не хватает - жесть... как только люди раньше жили.

Сегодня с утра друг hedgehog порадовал ссылочкой. Хочу такой субноут, но пока боюсь мне не до того. :) Судя по описанию ничего революционного с линуксом они не сделали, думаю Gentoo встанет без проблем, а ярлыки на стол я и сам могу поставить.

А еще друг SadKo намедне тоже порадовал другой ссылочкой. Must bookmark :) всем писателям операционных систем.

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

Модель/Вид

Потихоньку осваиваюсь с QT. Многие вещи еще не понятны, но постепенно начал въезжать в сабж от QT. Сделали они мощно.

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

Пока пытался заставить свою модель работать, чуть всю голову не сломал, если бы не ModelTest. Правда некоторые непонятки еще мучают меня. Например у меня что-то не получилось поставить два шортката на один QAction... Интересно, это можно сделать?

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

Ну начало положено, дальше наверное будет легче. :)

четверг, 1 ноября 2007 г.

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

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

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

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

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

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

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

четверг, 25 октября 2007 г.

Мульт.

Занимаясь с ребенком задумали снять мультфильм. Один мультфильм на 15 секунд мы уже делали, но думаю, что надо подойти к делу серьезнее.

Кадры мультфильма раскладываются по сценам. В каждой сцене список фреймов с длительностью каждого. Специальный скрипт перегоняет список фреймов с длительностью в список фреймов для mencoder. Который в свою очередь за два прохода создает качественную avi.

Озвучка для каждой сцены состоит из отдельных вавок, которые с помощью sox (опция pad позволяет сдвигать начало) миксуются в единую вавку. Которая на втором проходе кодирования видео закатывается в avi.

В корневом каталоге естественно находится Makefile, который позволяет все это автоматизировать. :)

Но че-то у меня mencoder последнее время глючит, видимо какие-то проблемы с драйвером контейнера avi, кодирую ровно минуту видео, А плейер потом показывает 4 минуты 31 секунду, а показывает всего мгновенье. Попробовал заместо lavc::mpeg4 использовать xvid - те же яйца, вид сбоку... Вероятно глючит сам контейнер. Вечером пропробую откатиться на прошлые версии mencoder. Ведь раньше я все кодировал без проблем... :( Страно это...


А еще для WorkMap и ради интереса я открыл проект на googlecode (там пока нечего смотреть). Надо сказать, что интерфейс code.google значительно проще, чем наворочанный sf... Да многим ли нужны эти навороты?

воскресенье, 21 октября 2007 г.

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

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

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

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

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

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

пятница, 19 октября 2007 г.

Создавая миры...

Поправить миру крышу, пока он еще вечен...
Екатерина Болдырева

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

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

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

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

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

Да и Он с уже не тот, что прежде. Теперь Он хотя бы знает что нужно делать и как это должно быть. В этот раз у него все получится...

PS: Я конечно не умею писать... не писатель, читатель наверное :) Просто аналогия позабавила, после чтения "Чистовик" Лукъяненко...

среда, 10 октября 2007 г.

И тут нелогично!

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

А как было бы удобно? Есть такая идея:
В большинстве своем переносные устройства всегда используются типично. То есть, воткнул, записал или прочитал что-то, выткнул. Ради вытыкания лезть мышкой на панель задач (не знаю как кто, но я копирую с клавиатуры) и говорить - отдай флэшку - НЕУДОБНО!

Чтобы было удобно для начала меняем для таких устройств алгоритм кэширования, который должен собственно работать так, чтобы максимально быстро сбрасывать записываемые данные на диск (мне даже кажется что так нужно делать для всех устройств, но это ИМХО). Дело осталось за малым... Вывести на панель задач индикатор. зеленая лампочка - диск готов к вытаскиванию, красная - не готов. И после записи файла на диск будет достаточно всего лишь дождаться пока диск позеленеет, после чего без всяких лишних телодвижений его можно вытаскивать.

А логика монтирования - может быть это просто пережиток прошлого?

вторник, 9 октября 2007 г.

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

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

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

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

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

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

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

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

четверг, 4 октября 2007 г.

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

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

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

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

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

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

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

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

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

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

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

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