Об этом блоге

Об этом блоге

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

среда, 22 апреля 2020 г.

Очередной технофашизм (нет)

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


Предыстория: в проекте есть некоторая система пользовательских прав, довольно простая. Права определяются правилами, описывающими доступы (как это описание парсится и обрабатывается — неважно). Правила атомарны, но их можно объединять в роли; и роли и правила могут быть прикреплены к пользователю.

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




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

Строятся разные предположения (неправильно написанное правило? ошибка парсера в граничном случае? козни тёмных сил?), но достоверно удаётся выяснить одно: правило срабатывает сразу после очистки кеша приложения или работает всегда при отключённом кешировании.

Нахожу по документации фреймворка возможную причину: класс обработчика правил связан с url-генератором (ему нужно проверять, куда идёт запрос), а url-генератор по умолчанию использует какое-то кеширование. Как точно всё это связано — непонятно, но отключение этого поведения вроде бы чинит проблему.

Но это не решение, поскольку влияет на скорость, и по хорошему — надо разобраться. Возможно, достаточно будет сбрасывать нужную часть кеша при добавлении правил. Берусь копать, и довольно случайно добираюсь до кода, который должен получить набор прав по id пользователя:

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static function xSqlForRulesByUser($attribute, $id = null): array
    {
        $id = $id ?? Yii::$app->user->id;
        $result = Yii::$app->cache->get($id."_rules");
        if (!$result) {
            $query1 = (new Query())
                ->select("ru__1.$attribute")
                ->from('auth_rules ru__1')
                ->innerJoin('auth_roles_rules roru1', 'roru1.id_rule = ru__1.id')
                ->innerJoin('auth_user_roles  usro1', 'usro1.role_id = roru1.id_role AND usro1.user_id = :u_id')
                ->addParams([':u_id' => $id]);
            $query2 = (new Query())
                ->select("ru__2.$attribute")
                ->from('auth_rules ru__2')
                ->innerJoin('auth_user_rules  usru2', 'usru2.id_rule = ru__2.id AND usru2.user_id = :u_id')
                ->addParams([':u_id' => $id]);
            $query1->union($query2);
            $result = (new Query());
            $s = $result->select("tmp.$attribute")
                ->distinct()
                ->from(['tmp' => $query1])
                ->column();
            Yii::$app->cache->set($id."_rules", $s, 3600);
            return $s;
        }
        return $result;

    }

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

Как бы поступил бы хороший разработчик: он бы воспользовался возможностями фреймворка, описав в ActiveRecord-моделях таблиц все связи между ними. В результате фреймворк построил бы близкий к оптимальному запрос на основании этих описаний. Более того: если бы при создании этих таблиц разработчик корректно указал им foreign keys, то генератор моделей и связи бы описал самостоятельно. Но если встретите такого разработчика — не спугните, это редкий вид, занесённый в красную книгу.
Как поступил бы средней руки кодер: сделал бы через ActiveRecord поиск в каждой из таблиц, а потом объединял результаты в array_merge(). Надо понимать, что "средний уровень" означает "наиболее часто встречающийся", а не "делающий норм".
Неопытный программист, не знающий фреймворк, написал бы сырой SQL-запрос, и почитав ответы на stackoverflow, делал бы запрос через $connection->createCommand("select * from...").

Но то, что написано здесь, находится за гранью добра и зла, а точнее — где-то в Восточной Бенгалии. Автор сих скорбных строк взял самые плохие стороны всех вышеперечисленных подходов и объединил их в этакого говнотрона.

Давайте же отринем брезгливость, и разберём им тут написанное.

Если перевести с тамильского на человеческий мысль, попытка выразить которую тут заложена, получится что-то вроде:
выбрать список прав из первой таблицы ($query1),
выбрать список прав из второй таблицы ($query2),
объединить результат (union()),
и из этого объединения выбрать список прав ещё раз, отфильтровав по уникальности (distinct()).

Способ, которым это сделано — ужасен. Во-первых, запросы написаны частично на SQL, а частично — на построителе запросов фреймворка. Это убивает все возможности навигации по коду: IDE не поймёт, какие таблицы тут задействованы, и не поймёт, что тут генерируется SQL-запрос, который можно бы было проанализировать. Да и человек не поймёт, если честно — читабельность никакая.
Во-вторых, SQL-запрос, который здесь генерируется, написан человеком, явно не понимающим, что такое реляционные базы данных. Тут, похоже, имеется нечто среднее между верой во всемогущество БД ("я как-нибудь объясню, чего я хочу, а движок всё за меня сделает лучшим образом") и похуизмом ("ну работает же!").

Сам получившийся запрос выглядит так:

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
SELECT DISTINCT
  `tmp`.`value`
FROM ((SELECT
      `ru__1`.`value`
    FROM `auth_rules` `ru__1`
      INNER JOIN `auth_roles_rules` `roru1`
        ON roru1.id_rule = ru__1.id
      INNER JOIN `auth_user_roles` `usro1`
        ON usro1.role_id = roru1.id_role
        AND usro1.user_id = 1)
  UNION
  (SELECT
      `ru__2`.`value`
    FROM `auth_rules` `ru__2`
      INNER JOIN `auth_user_rules` `usru2`
        ON usru2.id_rule = ru__2.id
        AND usru2.user_id = 1)) `tmp`


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


(для базового понимания признаков хуёвости достаточно ознакомиться с вот этой статьёй)

и статистику исполнения:


Три временные таблицы (одна на join, одна на union и одна на distinct), и 342 вставки в них. Вставки у запроса, которому нужно "просто спросить"!
Безусловно, один такой запрос БД не нагнёт. Но время его выполнения будет расти пропорционально количеству записей в таблицах (в геометрической прогрессии, если я правильно прикинул), а вызывается он, напомню, постоянно.

Думаю, это отличный пример того, как делать не надо; теперь можно ответить на вопрос "а как надо?".

Надо, как я и писал выше, указать связи между ActiveRecord-моделями задействованных таблиц (пользователи/правила/роли):

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<?php
declare(strict_types = 1);

namespace app\models;

use yii\db\ActiveQuery;
use yii\db\ActiveRecord;
use yii\helpers\ArrayHelper;

/**
 * ...
 *
 * @property ActiveQuery|AuthRolesRules[] $relAuthRolesRules -- связь к набору прав, входящих в роль
 * @property ActiveQuery|AuthUserRoles[] $relAuthUserRoles -- набор ролей, в которые входит право
 * @property ActiveQuery|AuthUserRules[] $relAuthUserRules -- связь к таблице пользователей, которым назначено это право напрямую
 */
class AuthRules extends ActiveRecord
{
    /*...*/

    /**
     * @return AuthRolesRules[]|ActiveQuery
     */
    public function getRelAuthRolesRules()
    {
        return $this->hasMany(AuthRolesRules::class, ['id_rule' => 'id']);
    }

    /**
     * @return AuthUserRoles[]|ActiveQuery
     */
    public function getRelAuthUserRoles()
    {
        return $this->hasMany(AuthUserRoles::class, ['role_id' => 'id_role'])->via('relAuthRolesRules');
    }

    /**
     * @return AuthUserRules[]|ActiveQuery
     */
    public function getRelAuthUserRules()
    {
        return $this->hasMany(AuthUserRules::class, ['id_rule' => 'id']);
    }
}


И через эти связи составить ActiveQuery-запрос:

1
2
3
4
5
6
7
AuthRules::find()
->distinct()
->select('value')
->joinWith(['relAuthUserRules directUsers', 'relAuthUserRoles rolesUsers'])
->where(['directUsers.user_id' => $userId])
->orWhere(['rolesUsers.user_id'=> $userId])
->all();

Который фреймворк преобразует в SQL-запрос:

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
SELECT DISTINCT
  `value`
FROM `auth_rules`
  LEFT JOIN `auth_user_rules` `directUsers`
    ON `auth_rules`.`id` = `directUsers`.`id_rule`
  LEFT JOIN `auth_roles_rules`
    ON `auth_rules`.`id` = `auth_roles_rules`.`id_rule`
  LEFT JOIN `auth_user_roles` `rolesUsers`
    ON `auth_roles_rules`.`id_role` = `rolesUsers`.`role_id`
WHERE (`directUsers`.`user_id` = 1)
OR (`rolesUsers`.`user_id` = 1)


Профилирование этого запроса показывает куда более приятную картину:




Хотя и не идеальную: для фильтрации уникальных результатов через DISTINCT, одна временная таблица всё-таки создаётся. Попытаться решить это можно по разному: подумать над условием, изучить структуру таблиц и подобрать оптимальный JOIN, настроить сервер MySQL на генерацию временных таблиц в памяти — это уже отдельная тема, в которой я не так уж и силён. Вполне нормальное решение — оставить, как есть, занявшись оптимизациями выше: достаточно сделать обращение к этому запросу не столь частым, и станет совсем хорошо.

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

среда, 27 марта 2013 г.

Пилим восьмибитный процессор. Часть седьмая, баголовная.

Я две недели не публиковал описаний прогресса разработки процессора.
Тем не менее, это не значит, что я им не занимаюсь - занимаюсь, хотя, пожалуй, уже без той остервенелой увлечённости, что в начале, плюс, отвлекаюсь на другие занятия, да ещё сидел без клавиатуры несколько дней. Но даже с учётом всего этого, две недели - срок вполне достаточный для накопления очередной порции интересных доработок.
Я так думал, да. Всего за пару дней я переделал микросхемы, определяющие тип операндов и их количество, переделал командный блок (переупорядочил команды, добавил новые), добавил новые регистры - и очевидных проблем при этом не проявлялось. Вылезали, конечно, кое-какие баги, не найденные раньше, но ничего серьёзного.
Так что я начал было заниматься командами перехода по памяти, которые сплошь однобайтные - и оказалось, что мой управляемый счётчик неправильно работает на операции, описываемой как for ($=0;$i==0;$i++) - то есть команды без операндов им не воспринимались, что вело к неправильному разбору всей дальнейшей памяти.
Окей, проблема локализована, надо только переделать счётчик...
Я потратил на это неделю.

Несложная, казалось бы, задача - а схема не давалась ни в какую. Подход "разбить на подзадачи и решить по отдельности" не работал - решённые подзадачи просто не склеивались в целое. Расписать логику схемы в виде набора логических функций, сократить вывод и реализовать получившееся схемой вовсе нельзя (вернее, можно, но это задача довольно громоздкая, и я бы только запутался).
Тогда я применил другой подход. Если задача не даётся - займись чем-нибудь другим. Пусть подсознание само решает задачу, тебе останется только проверять выдаваемые им варианты. Что, вы так не умеете? Ха-ха, неудачники!
Прошло время, подсознание действительно выдало вариант решения (уже не помню какого, да и не важно). Я открыл схему, прогнал тестовую программу, чтобы освежить в памяти структуру - а схема-то и не работает.
То есть, допустим, какой-то простой код, вроде mov a,1h не работал совсем. При этом вся логическая цепочка работала как надо, на всех контактах были правильные значения, а нужный регистр не устанавливался и всё. Странно, как и то, что раньше-то это работало - более того, при откате не предыдущую версию схемы работало тоже.
Значит что? Значит накосячил где-то при доработках, и проглядел косяк. Попробовал поискать - нету. А различий с последним рабочим образцом накопилось уже достаточно, и разобраться, какие из них являются причиной бага уже довольно трудно.
В общем, я плюнул, откатился на последнюю рабочую версию, и стал переносить доработки понемногу, усиленно тестируя схему после каждого изменения. Снова переделал микросхемы и командный блок, всё выглядело чисто. В недоумении я хотел уже было браться за блок регистров, но тут мне "повезло" (если так можно выразиться) - одна из тестовых программ давала сбой. Программа примерно такая:

MOV REG1,VALUE ;изменяем любой регистр, не обязательно через MOV
SHL REGx,VALUE ;регистр может быть указан любой, не обязательно тот, что в предыдущей команде

Первая команда выполнялась безупречно, а на момент чтения (даже не выполнения!) первого операнда второй команды REG1 обнулялся. Путём перебора, выяснилось, что такой же баг вызывают некоторые другие операнды во второй команде, например SUB и XOR. А, скажем, SUM проходила нормально. Поэкспериментировав, я выяснил, что и не команда даже влияет на появление бага, а полный байт команда+типы параметров; причём последовательности значений "бажных" байт не выглядели хоть как-то осмысленно. Например, значения с 53h до 57h приводили к ошибке, значения в промежутке 58h-63h ошибки не вызывали, а значения выше 63h - опять приводили к багу.
Логики никакой. Да даже и не в том, дело, какая последовательность вызывает ошибку, дело в том, что процессор попросту не мог такую ошибку допустить. У него есть нога EXECUTE, сигнал на которой вызывает выполенение буферизованной команды. Если на ноге нет сигнала - состояние процессора не меняется. Вот эта нога выделена на развёрнутой схеме:


Клик для увеличения

Как видите, n-транзисторы просто отсекают процессор от буфера, так что совершенно не имеет значения, что там "вовне" - если, конечно, на ноге ноль. А на ноге был ноль (сигнал появлялся только тогда, когда счётчик доходил до нужного значения), но процессор всё время вёл себя по разному.
Ошибки не было - и, в то же время, она была. Я потратил уйму времени и нервов, пытаясь разобраться, и был уже близок к тому, чтобы сдаться, признав, что ошибка где-то в Logisim.
Хорошо, что подсознание и тут предложило мне вариант. "Может быть - подумал я - счётчик и вправду выдаёт на выход EXECUTE сигнал, но тут же убирает его?".

Взглянем снова на схему счётчика:


В начальном состоянии на элемент И подаётся единица с компаратора и ноль с тактового входа. При первом такте с тактового входа придёт единица, а с компаратора - ноль. Если значения меняются одновременно, то после И реузльтат всё равно не изменится (0&1==1&0), как и требуется. Но вдруг одновременности не существует?
Забегая вперёд, скажу, что так оно и есть. В справке Logisim, в разделе "Задержки логических элементов" читаем в описании схемы, похожей на нашу:

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

Так как же проверить такое поведение? Вариант предложен там же, в справке (к собственному удовольствию я дошёл до него самостоятельно): подключить к выходу триггер, и посмотреть, изменится ли его значение, или нет:


Бах! Триггер переключается - а, значит, ошибка вызвана именно тем, что счётчик подаёт сигнал исполнения не тогда, когда требуется. Что же, процитирую справку ещё раз:

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

Почему же этот баг не проявлял себя раньше? Точно не знаю, но думаю, что просто не успел - слишком проста была схема процессора. Впервые проявлять он себя начал, видимо, уже после усложнения, что и заставило меня начать разбираться.
Устранить баг можно, но не нужно. Счётчик всё равно требуется переделывать. А переделка его мне никак не давалась - о чём я уже жаловался выше.
Помучавшись так и эдак, я применил такой подход: описал требуемую логику счётчика на псевдокоде (хотя, какой, к чёрту, псевдокод, это PHP), и попробовал потом описать этот код логической схемой (это всё равно, что строить блок-схему). Код получился такой:

  1. $COMMANDS=array(2,10,12,0,2,11,13,1,15,1,18,0,2,9,7);
  2. $return=array();
  3. $set=TRUE;
  4. $EXEC_FLAG=FALSE;
  5. $i=0;
  6. while (TRUE) {
  7. if ($EXEC_FLAG) {
  8. echo "-->EXEC ";
  9. print_r ($return);
  10. $EXEC_FLAG=FALSE;
  11. $return=array();
  12. }
  13. if ($set) {
  14. $for=$COMMANDS[$i];
  15. echo "!$for ";
  16. $lim=$for;
  17. $set=FALSE;
  18. $cnt=0;
  19. }
  20. echo ":$cnt ";
  21. $return[$cnt]=$COMMANDS[$i];
  22. if ($cnt==$lim) {
  23. $EXEC_FLAG=TRUE;
  24. $set=TRUE;
  25. $i++;
  26. continue;
  27. }
  28. $cnt++;
  29. $i++;
  30. }

$COMMANDS - массив, содержащий количества операндов при интерпретации ячейки памяти, как команды. Остальное, думаю, очевидно.
А вот схема, которая этот код реализует. Названия элементов соответствуют названиям переменных в коде, у регистра lim срабатывание переключено на высокий уровень (т.е. он обновляется не по переключению такта, а всегда, пока на тактовом входе есть сигнал). EXEC_FLAG и set - T-триггеры (в отличии от D-триггера они не устанавливают поданное на вход значение, а переключают собственное, т.о. их удобно использовать в качестве "флагов").


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

четверг, 21 марта 2013 г.

Грустная сетевая футурология


Картинка для привлечения внимания

Пройдёт время, и происходящий ныне сетевой беспредел будет вспоминаться с некоторым недоумением - "а что, неужели и правда была цензура?". Вернее - вспоминаться не будет, как не вспоминается ныне засилье падонкоффского сленга, или даже недавний совсем шухер с Фукусимой. Останется напоминанием только статейка в википедии с упоминанием наиболее значимых вех развития цензуры и финальной датой её отмены.
К сожалению, эту дату вам не назовёт сейчас никто - по крайней мере, пока у власти находится незаконно самоназначившее себя правительство, во главе с ботоксным крошкой Цахесом. И вполне очевидно, что сейчас даже не пик активности, а только начало разгона информационно-блокирующей машины, которое вполне может вылиться в то, что уже существует в Китае. В вариант полного запрета интернета я всё-таки не верю - и не потому, что технически это нереально, а потому, что это лишит хозяев телекомов больших доходов.
Но хватит о политоте, давайте пофантазируем как жить в условиях грядущей тотальной информационной цензуры.

Способ нулевой, патриотическо-системный.
Общеизвестно: в сети нет ничего стоящего. Там только гомосексуалисты, наркоманы, педофилы, оппозиция и самоубийцы. Поэтому способ заключается в том, чтобы выпить "Путинки" и принять дозу информации из первого православного телеканала.
Что дальше: ничего, это первая стадия, она же - финальная.

Способ первый, анонимный.
Тотальный переход в распределённые анонимные сети. TOR, I2P, Freenet. Реалистичный, уже на текущий момент, вариант.
Что дальше: анонимные сети получают резкий толчок развития, пользоваться ими научится любой чайник, как, в своё время, это произошло с торрентами. Интерфейс софта упростится (сейчас ещё есть что упрощать), система станет удобнее, внутрисетевые скорости вырастут за счёт увеличения числа юзеров. Стопятьсот кубических зигабайт нецензурируемого киберпространства, где будут свои аналоги ютубов с ЦП, спокойно соседствующие с безобидными форумами любителей игры в "Космических рейнджеров" (где, как известно, можно торговать наркотиками, и даже употреблять вещества, так что и игру, и её обсуждения обязательно запретят).
Однако, выходить через TOR в "нормальный" интернет будет всё сложнее и сложнее. Туннели будут отслеживаться и блокироваться на магистральном уровне (реализуют уж как-нибудь). Рунет расслоится, и приватные сети (вернее - одна большая скрытосеть) будут существовать отдельно от плавающего на поверхности цензурированного добра.
Конечно же, скрытосети объявят вне закона.
Доступ в сеть будет предоставляться только при наличии специальной шпионской программы, установленной на пользовательском устройстве. Программа будет отслеживать попытки подключения к скрытосетям, и стучать об этом, сломать же её будет крайне сложно - она будет обновлять саму себя с провайдерского сервера каждый раз.
Но что с выходом в международные интернеты? Естественно, международный траффик будет поначалу просто фаерволлиться (как в Китае). Найдут способ резать VPN, вполне возможно - начнут ограничивать доступ к неподконтрольным IP (введут белые списки, вместо чёрных).
В конце концов, скрытосети если и не победят совсем, то затруднят их работу настолько, что пользоваться ими станет даже менее комфортно, чем сейчас.

Способ второй: олдфажно-векторный.
Поскольку каналы выхода в сеть прямо или косвенно контролируются правительством, вполне очевидным решением будет создание собственных каналов и собственных сетей. И это не то, чтобы нереалистично - напротив, именно в этом виде существовала сеть в свои золотые годы. Правда, это была другая сеть, нежели интернет - я говорю о Фидонет (и прочих левонетах).
При этом вовсе не обязательно откатываться на FTN-технологии образца девяностых, достаточно заимствовать принципы, подстроив их под реалии современности. Телефонная линия сейчас есть не у каждого, зато почти у всех есть WiFi. Wimax-оборудование тоже вполне доступно, ну и старые-добрые домовые сети с лапшой меж этажами тоже никто не отменял, много где они вполне ещё живы. В конце концов - можно и достать с полок старинные "Зуксели", да и флоппинеты вполне можно возродить.
Конечно, нужно решить проблему роутинга в таких сетях, но это тема отдельной статьи. В комменты к блогозаписи кастуется Мицгол, мне крайне любопытно, что гуру скажет по этому поводу.
Естественно, организация таких сетей будет жесточайше караться. Потому сети надо планировать так, чтобы они были как можно более децентрализованными. Ну не смогут же ловить всех, кто шифрованный радиоканал до соседского дома сделал (хотя попытки наверняка будут).

Способ третий: конспирационно-несуществующий.
Создаётся ресурс, вполне себе доступный по обычному IP. Ресурс представляет собой этакие концентрированные интернеты - там и социалочка, и бложеки, и свои ютубы, и прочие ништяки.
Но вход внутрь только для "своих", по логину, паролю и отпечатку пятки. Остальные видят фото котят, играющих с президентом в бадминтон.
Попасть внутрь можно только по приглашению "своего" с поручительством двух партийных. За упоминание о бойцовском клубе ресурсе за его пределами - обстракция и исключение из партии. За вынос информации вовне - аналогично.
Минусы очевидны, и с некоторой стороны даже выглядят плюсами. Запретить доступ к ресурсу - как бы незачто, пока вовнутрь не попадёт чиновник. При достаточном соблюдении конспирации, ресурс будет жить достаточно долго,.
Я более чем уверен, что такой ресурс уже есть (и это не лепра), и если магистр ордена решит меня пригласить, то пусть пишет в личку.

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

Послесловие.
Я фантазировал "что", но не говорил "как". Свои "каки" и "чтоки" предлагайте в комментариях.

среда, 13 марта 2013 г.

Пилим восьмибитный процессор. Часть шестая: улучшение архитектуры и снова ассемблер.

После вынужденного перерыва снова возвращаюсь к своей архиувлекательной разработке. Оставил я её в каком-то промежуточном состоянии: например, минимальный набор команд реализован, возможность менять значения в памяти есть - а перехода на нужный адрес нет (хотя всё необходимое для реализации такой команды есть, саму команду я не запилил).
Непорядок.
В общем, я достаточно долго думал и прикидывал, что делать дальше, и как лучше это что делать. Пришёл к следующему выводу: нужно менять структуру команд, пилить уже условные переходы и циклы. После этого - уже всё, настоящий хардкор.
Что плохо в текущих командах? Они были взяты от балды, и шли не в логическом порядке: скажем за логическим XOR шло арифметическое SUM, потом опять логический SHL. Добавь я сейчас команду SUB (вычитание) - её пришлось бы помещать вновь за логической командой, а не рядом с SUM, где ей самое место. Нет, если пользоваться ассемблером - то пофиг, в каком порядке идут опкоды, но при трейсе обработки команд с упорядоченными командами удобнее.
Дальше: команда NOP. Много ли можно придумать программ, где ничего не делающий операнд реально нужен? В крайнем случае для пропуска такта можно использовать MOV A,A.
Итого я пересмотрел набор команд, и выглядит теперь он так:

ОпкодКомандаОписание
0x0 MEM Переходы по памяти
0x1 MOV Пересылка значения
0x2 XOR Логическое ИЛИ-НЕ
0x3 OR Логическое ИЛИ
0x4 AND Логическое И
0x5 SHL Левое смещение
0x6 SHR Правое смещение
0x7 SUM Арифметическое сложение
0x8 SUB Арифметическое вычитание
0x9 MUL Арифметическое умножение
0xA DIV Арифметическое деление
0xB STACK Работа со стеком
Описание команд переходов и работы со стеком чуть ниже.
Как видите - изменился и набор и порядок. При этом пока четыре опкода остаются свободными - я даже не знаю, какие команды можно ими задать. Возможно, при расширении архитектуры появятся какие-то команды (например опкод, выводящий "Hello, world!", таким образом, делающий возможным написание такой программы размером в один байт).
Думаю, с опкодами 0x1 - 0xA вопросов не возникло. Другое дело - 0x0, обозначающий различные переходы по памяти. Как одной командой можно закодировать их все?
Тут стоит вспомнить, как переходы реализованы в x86. Самый простой, безусловный переход вызывается так:
JMP @ADDRESS
где ADDRESS указывает на адрес в памяти, на который нужно совершить переход.
Соответственно, команда в памяти представлена двумя последовательностями бит: одна кодирует команду JMP, другая шифрует адрес. Просто и логично.

Условные переходы реализованы сложнее, и состоят из двух команд. Первая: CMP (compare) - она сравнивает два операнда (вычитая один из другого), в зависимости от результата сравнивания изменяя специальные флаги во флаговом регистре. А команда условного перехода (их больше десятка, и включены даже такие, как "перейти, если чётно") уже проверяет эти флаги и переходит (или не переходит) по указанному адресу.
Сложно? Не особенно, но, в общем, сложнее, чем могло быть. И хотя у такого решения наверняка есть свои плюсы, это совершенно не значит, что его необходимо копировать.
Тем более, что у нас не большой и жирный x86, у нас слабый и виртуальный meighty, и раздавать по опкоду на каждую команду перехода просто нельзя (да ещё опкод на команду сравнения). Выход достаточно очевиден: сравнивать значения, которые всегда находятся в одном и том же месте - и, применительно к процессору, такими "местами" могут стать только регистры. Также в определённом регистре можно сохранять адрес, на который необходим переход.
Допустим, такие регистры уже есть. Тогда любая команда условного или безусловного перехода не нуждается в параметрах, а это значит, что четыре младших бита из командного байта, которые использовались под обозначение типа операнда, можно отдать под команды! Так что в один опкод 0x0 может уместиться 16 команд перехода по памяти - чего более, чем достаточно, для реализации любых условий. Я реализовал следующие условия:
[7-4][3-0]КомандаОписание
0x0 0x0 JMP Безусловный переход
0x0 0x1 JE Переход при равенстве операндов
0x0 0x2 JNE Переход при неравенстве операндов
0x0 0x3 JL Переход, если первый меньше
0x0 0x4 JG Переход, если первый больше
0x0 0x5 JLE Переход, если первый меньше или равен
0x0 0x6 JGE Переход, если первый больше или равен
Само собой, перед сравнением и переходом нужно задать значения для сравнения и адрес для вероятного перехода, для чего нужно использовать команду MOV.
Аналогичный подход реализован и со стековыми командами. Их запланировано четыре: PUSH (поместить в стек), POP (извлечь из стека), PEEK (изменить значение на верхушке), POKE (удалить значение с верхушки). Параметр у всех стековых команд может быть только один, поэтому ничего не мешает отдать два бита на кодирование команд:
[7-4][3-2][1-0]КомандаОписание
0x0 0x0 {TYPE} PUSH Поместить на вершину стека
0x0 0x1 {TYPE} POP Взять с вершины стека
0x0 0x2 {TYPE} PEEK Изменить вершину стека
0x0 0x3 {TYPE} POKE Удалить вершину стека
Но к стеку я вернусь ещё не скоро (его единственное предназначение - оптимизация рекурсивных вызовов, для полноценного вычислителя он не нужен), а для переходов нужны эти самые регистры.
Можно поступить так, как поступили разработчики Intel: дать каждому пользовательскому регистру своё дополнительное назначение (я без шпаргалки помню только AX - аккумулятор и CX - счётчик). Меня всегда это смущало: вот использую я регистр (который выступает в роли сверхбыстрой надоперативной памяти) для своих целей, и тут какая-нибудь команда ждёт, что я через этот регистр буду передавать ей параметр! В общем, мне всегда хотелось разделить регистры на чисто пользовательские (с которыми программист или компилятор ЯВУ может работать, как ему вздумается, и которые процессором не используются более никак), на служебные (с которыми можно работать, но которые могут выступать параметрами команд) и внутренние (которые используются процессором под свои нужды, и изменять значения которых не рекомендуется или вовсе нельзя, например, стековый указатель).
Собственно, ничего не мешает мне сделать именно так. На адресацию регистров выделен целых восемь бит, сейчас регистров восемь, и для их кодирования достаточно трёх бит. Добавлю ещё восемь служебных регистров S0-S7, которые будут кодироваться числами от 0x8 до 0xF - и никаких проблем. Три первых регистра щедро выделяю под операнды команд условных переходов: S0 пусть содержит первое сравниваемое значение, S2 - второе, S3 - адрес перехода.

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

И вроде бы всё хорошо, но есть один маленький нюанс: все операции с памятью (чтение, запись, переход) сейчас возможны только по абсолютным адресам, заданным константой. О том, чтобы ссылаться на адреса переменными я попросту не подумал; к счастью не поздно исправить эту ошибку, убрав тип операнда "порт", и добавив тип операнда "адрес, указанный в регистре". Тип операнда "порт", если помните, был всунут для того, чтобы не пропадало значение, освободившееся после отказа от командной работы со стеком. Портов у нас нет, и отказаться от этого типа можно безболезненно (реализовать ввод-вывод в порты можно будет и отдельными командами). Так что теперь типы операндов выглядят так:
binhextype
00 0x0 Константа
01 0x1 Регистр
10 0x2 Адрес в памяти, заданный константой
11 0x3 Адрес в памяти, заданный в регистре
Как видите, я также передвинул тип операнда "адрес, заданный константой" - так попросту логичнее. Это изменение потребует переделки схем Operand selector, Data selector, и, возможно, других - но об этом позже.

До того, как воплощать новые команды и новые регистры в виртуальном кремнии, я доработал ассемблер - программы получаются совсем уж сложные, писать их в опкодах долго и муторно. Изменения и добавления следующие:
- Чуточку поменялся синтаксис: портов больше нет, и символ @ отдан под обозначение меток.
- Для команды SUM добавлен алиас ADD (т.е. можно писать и так и эдак).
- Добавились операнды новых регистров (S0-S7) и все перечисленные выше команды.
- Также, как понятно из вышенаписанного, добавились метки. Метки позволяют не считать размер команд и адресов перехода "на пальцах" - ассемблер делает это сам (для чего пришлось реализовать подобие линковщика). Метки регистронезависимы, т.е. LABEL, label, Label и LaBeL - это одна и та же метка. Как работают метки понятно из нижеприведённого исходника.
- Появилась поддержка комментариев (всё, что после ; считается комментарием).
- Ну и заодно ассемблер выводит портянку команд вместе с адресами и метками, а вывод бинарного представления команд я убрал (он нафиг не нужен).
Вот как будет выглядеть программа, реализующая перезапись самой себя степенями двойки от 2^0 до 2^7:
START:   ;Метка начала выполнения программы
 MOV A,1h ;Нулевая степень двойки (и любого другого числа) - это 1.
 MOV B,0h ;В регистре B будет адрес ячейки памяти, в который нужно записать вычисленное значение
FOR:   ;Метка цикла
 MOV S1,80h ;Ограничение выполнения: седьмая степень двойки, больше целых степеней в восемь бит уже не уместится.
 MOV S2,A ;Записываем текущее значение в служебный регистр для сравнения
 MOV S3,@END ;Записываем в служебный регистр метку, на который нужно будет перейти по условию
 JE  ;Если S1=S2 то переход на метку END
 MOV [B],A ;Записать по адресу, содержащемуся в регистре B значение регистра A
 SHL A,1h ;Левое смещение двоичного числа на одну позицию - это умножение его на 2.
 SUM B,1h ;Увеличиваем значение регистра B
 MOV S3,@FOR ;Адрес метки
 JMP  ;На которую и совершается переход при очередной итерации
END:   ;Выход из цикла
 MOV [B],A ;Последняя запись в память, и конец программы.


Клик для увеличения
Я специально написал избыточный код, для того, чтобы было легче продемонстрировать следующую возможность ассемблера.
Заметно, что задавать условия переходов несколькими командами неудобно, к тому же такая запись ухудшает читаемость программ. Поэтому для условных и безусловных переходов сделан краткий вариант записи.
Для безусловного перехода, вместо
MOV S3, ADDR
JMP
можно писать
JMP ADDR
Для условных переходов, вместо
MOV S1,VALUE1
MOV S2,VALUE2
MOV S3,ADDR
CMD
можно писать
CMD VALUE1,VALUE2,ADDR

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

START:
 MOV A,1h
 MOV B,0h
FOR:
 JE 80h,A,@END
 MOV [B],A
 SHL A,1h
 SUM B,1h
 JMP @FOR
END:
 MOV [B],A


Клик для увеличения

Этот код тоже не является оптимальным - например, нет нужды каждый раз делать присвоение MOV S1,80h, да и цикл можно организовать удобнее. Но пока и этого достаточно.
Побаловаться ассемблером и поискать в нём ошибки можно всё там же. Следующую часть постараюсь сделать "железячной", рассказав о реализации логики, способной такие программы выполнять.
Продолжение следует.

вторник, 5 марта 2013 г.

Пилим восьмибитный процессор. Часть пятая: ассемблер, тесты, запуск.

Небольшое предисловие, которое должно было быть в самой первой статье по этой теме:
Я понятия не имею, как правильно проектировать процессоры. И как неправильно - тоже. Я просто играюсь в конструктор, делаю ошибки, перекраиваю схемы на лету и наслаждаюсь этим забавным и увлекательным процессом.
Перечитывая предыдущие части, я нахожу в них заметное количество косяков и откровенных глупостей. Скажем, я так и не определился с архитектурой процессора, вроде сначала задумав сделать что-то RISC-подобное, но временами замахиваясь на CISC, и огребая от сложности реализации откатывался обратно. В итоге же получается, что я во многом копирую единственную знакомую мне архитектуру x86.
Поэтому: эти статьи рассказывают о том, как делаю я, а не о том, как надо.

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


Не очень-то впечатляет =). Но если раскрыть схемы, и представить всё это добро вместе, получится вот так:


Клик для увеличения

Я не стал раскрывать все подсхемы (в которых, в свою очередь, есть ещё подсхемы) - по-моему и так внушительно. Даже Шмигирилову показать не стыдно.
Несколько комментариев к схеме.
- Выход Execute end сделан на будущее. В дальнейшем он будет сигнализировать о том, что процессор выполнил очередь команд и ждёт новых инструкций. Пока же все инструкции выполняются за один так, так что смысла в подобной сигнализации нет.
- Выход ERR - это зачатки системы контроля ошибок. Сейчас на него подаётся сигнал в единственной ситуации: если попытаться работать с памятью на ввод и вывод одной инструкцией (пример: MOV [addr],[addr]).
- В процессе отладки (который я ещё буду описывать) была найдена незначительная ошибка: в блоке команд не стояло несколько согласующих резисторов, отчего невозможны были операции с памятью. Эта ошибка присутствует на схемах, приведённых в предыдущей статье.
- Индикаторы, если кто ещё не догадался, показывают значения регистров и предназначены только для увеличения удобства.
- Память и ядро работают на одной частоте, несмотря на то, что тактовые генераторы у них разные. Теоретически, ничто не должно мешать работать им на разных частотах (если память будет работать быстрее - нужно будет ввести простенький механизм ожидания выполнения), но logisim не позволяет задавать разные частоты двум элементам.

Пожалуй, можно переходить к тестированию, которое, как решено выше, должно заключаться в передаче процессору всех вариантов корректных команд. Такой набор можно сгенерировать вручную, а можно - и даже нужно - написать ассемблер, переводящий читаемые команды в машинный код.
На реализацию этого ассемблера на PHP ушло около часа, побаловаться можно здесь Meighty assembler (название "Meighty" у меня получилось из объединения слов might и eight, так я и назвал свой процессор). Команды вводить в чёрное окошко, жать compile. При удачной трансляции слева от окна появится двоичный байткод, снизу - его шестнадцатеричное представление, которое можно копипастить в logisim (буквально, его компонент ОЗУ корректно воспримет вставку таких данных), при ошибке выдастся описание проблемы.


Клик для увеличения

Ассемблер имеет intel-like синтаксис, регистр значения не имеет, все лишние пробелы игнорируются. Числовые значения задаются только в шестнадцатеричной системе счисления, десятичная и двоичная, возможно, будут сделаны потом. Операнды перечисляются через запятую, и задаются следующим образом:
- константа: значениеH, например 10H, FDH, 7h;
- регистр: идентификатор регистра от A до H;
- порт: @номер портаH, например @03H, @88h;
- адрес в памяти: [адресH], например [12h], [FFH], [0H];
Ассемблер пытается отлавливать ошибки, как синтаксические, так и логические, можете поиграться. Комментарии не реализованы. Порты, как понимаете, тоже отсутствуют, выполнение команд чтения-записи для них смысла не имеет.
Пример программы (абсолютно бессмысленной, её цель только продемонстрировать работу):
MOV A,10h
MOV B,A
SUM B,3h
MOV [20h],B
MOV C,[20h]
SHL [20h],2h
XOR A,[20h]
NOP

и т.д.
Меня КРАЙНЕ ломает делать гифку, которая продемонстрировала бы, что эта, да и все другие допустимые программы, выполняются корректно. Гифкоклепание займёт не меньше часа, так что предлагаю просто скачать logisim, взять мою схему и посмотреть всё самим.

Что дальше? Примерно вот что:
- реализация восьми дополнительных служебных регистров вдобавок к восьми имеющимся, которые останутся пользовательскими. Служебные регистры будут предназначены, прежде всего, для организации работ программ в памяти (требуется разделять код и данные - значит нужны аналоги CS и DS) и возможного её увеличения (для адресации за пределами двух килобайт можно ввести сегментацию, тогда понадобится регистр, указывающий на текущий сегмент), а также для выполнения команд условного перехода (команда будет сравнивать два определённых регистра), ну и давно задуманный флаговый регистр. Возможно - счётчик (это будет зависеть от того, как я реализую циклы).
- стек. Его я, как и было задумано ранее, всё-таки реализую на отдельной схеме - пусть будет хоть какое-то значимое отличие от x86. На реализацию четырёх стековых команд (стандартные POP, PUSH, не очень стандартная PEEK и совсем не стандартная POKE) понадобится всего один опкод (т.к. параметр у этих команд будет всегда один, два неиспользуемых бита можно отдать под команду).
- команды условного и безусловного перехода.
- дополнительные команды обработки данных (SUB, MUL, DIV, NOT).
- доработка ассемблера.
- отлов и обработка ошибок.
- ASCII-терминал.

Дальше можно будет думать о простой системе прерываний (например, наборе подпрограмм, зашитом в ПЗУ), но я уже не уверен, что меня на это хватит.
Продолжение, скорее всего, следует.