Предыдущая статья серии была посвящена теории парсинга исходников с использованием ANTLR и Roslyn. В ней было отмечено, что процесс сигнатурного анализа кода в нашем проекте PT Application Inspector разбит на следующие этапы:

1. парсинг в зависимое от языка представление (abstract syntax tree, AST);
2. преобразование AST в независимый от языка унифицированный формат (Unified AST, UAST);
3. непосредственное сопоставление с шаблонами, описанными на DSL.

Данная статья посвящена второму этапу, а именно: обработке AST с помощью стратегий Visitor и Listener, преобразованию AST в унифицированный формат, упрощению AST, а также алгоритму сопоставления древовидных структур.

Содержание

• Обход AST
  
  • Visitor и Listener
  • Различия в Visitor в ANTLR и Roslyn
  • Грамматика и Visitor в ANTLR
  • Альтернативные и элементные метки в ANTLR
• Типы узлов унифицированного AST
• Тестирование конвертеров
• Упрощение UAST
• Алгоритм сопоставления древовидных структур
• Заключение

Обратите внимание, что хотя пост написан от первого лица, это перевод статьи из блога Jimmy Bogard, автора AutoMapper.

Меня часто спрашивают, особенно в контексте архитектуры вертикальных слоев (vertical slice architecture), где должна происходить валидация? Если вы применяете DDD, вы можете поместить валидацию внутри сущностей. Но лично я считаю, что валидация не очень вписывается в ответственность сущности.

Часто валидация внутри сущностей делается с помощью аннотаций. Допустим, у нас есть Customer и его поля FirstName/LastName обязательны:

public class Customer
{
    [Required]
    public string FirstName { get; set; }
    [Required]
    public string LastName { get; set; }
}

Проблем с таким подходом две:

• Вы изменяете состояние сущности до валидации, то есть ваша сущность может находиться в невалидном состоянии
• Неясен контекст операции (что именно пытается сделать пользователь)

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

Сегодня давайте поговорим о преимуществах Postgres перед другими системами с открытым кодом. Эту тему мы обязательно раскроем более подробно на PG Day'16 Russia, до которой осталось всего два месяца.

Возможно, вы спрашиваете себя: «Почему PostgreSQL?» Ведь есть и другие варианты реляционных баз данных с открытым исходным кодом (в рамках этой статьи мы рассматривали MySQL, MariaDB и Firebird), так что же Постгрес может предложить такого, чего нет у них? В слогане PostgreSQL заявляется, что это «Самая продвинутая база данных с открытым исходным кодом в мире». Мы приведем несколько причин, почему Постгрес делает такие заявления.

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

Опять вернёмся в традиционную область разработки операционных систем (и приложений для микроконтроллеров) — написание драйверов.

Я попробую выделить некоторые общие правила и каноны в этой области. Как всегда — на примере Фантома.

Драйвер — функциональная компонента ОС, ответственная за отношения с определённым подмножеством аппаратуры компьютера.

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

В современной реальности, конечно, всё сложнее. Драйвер — типичный инстанс-объект класса, и классов этих до фига и больше. В принципе, интерфейс драйверов пытаются как-то ужать в прокрустово ложе модели read/write, но это самообман. У драйвера сетевой карты есть метод «прочитать MAC-адрес карты» (который, конечно, можно реализовать через properties), а у драйвера USB — целая пачка USB-специфичных операций. Ещё веселее у графических драйверов — какой-нибудь bitblt( startx, starty, destx, desty, xsize, ysize, operation ) — обычное дело.

Цикл жизни драйвера, в целом, может быть описан так:

• Инициализация: драйвер получает ресурсы (но не доступ к своей аппаратуре)
• Поиск аппаратуры: драйвер получает от ядра или находит сам свои аппаратные ресурсы
• Активация — драйвер начинает работу
• Появление/пропадание устройств, если это уместно. См. тот же USB.
• Засыпание/просыпание аппаратуры, если это уместно. В контроллерах часто неиспользуемая аппаратура выключается для экономии.
• Деактивация драйвера — обслуживание запросов прекращается
• Выгрузка драйвера — освобождаются все ресурсы ядра, драйвер не существует.

(Вообще я написал в прошлом году черновик открытой спецификации интерфейса драйвера — см. репозиторий и документ.)

Мне известны три модели построения драйвера:

• Поллинг
• Прерывания
• Нити (threads)

Сегодня мы хотим поговорить о сокровенном — у нас есть API.

Мы писали, а затем переписывали его заново на протяжении четырех лет. И за это время прошли почти все классические стадии “принятия неизбежного”. Кроме одной — четвертой. И хотим поделиться нажитыми непосильным трудом выводами, что делать и не делать, если вы решите делать свой “мощный эпиай”.



Процесс создания API uCoz иногда напоминал сюжет сериала The Knick («Больница Никербокер») — с неудачными операциями, кишками и экспериментами на живых людях.

Стадия первая – Отрицание

В процессе работы над ОС Фантом, которая вообще не Юникс никаким местом, мне, тем не менее, захотелось сделать в нём Unix-compatible подсистему. Не то, чтобы прямо POSIX, но что-то достаточно близкое. Отчасти из любопытства, отчасти для удобства, отчасти как ещё один migration path. (Ну и вообще было интересно, насколько трудно написать простенький Юникс «из головы».) В качестве цели номер 1 была поставлена задача запустить quake 1 for Unix, которая и была достигнута.

В процессе, естественно, появились open/close/r/w/ioctl, и появилось ощущение, что последний неприлично, постыдно устарел. В качестве упражнения для размятия мозга я реализовал (в дополнение к обычному ioctl) некоторый альтернативный API, который бы позволил управлять свойствами устройств более гибким и удобным с точки зрения пользователя способом. Этот API, конечно, имеет свои очевидны минусы, и, в целом, эта статья — RFC, aka request For Comments.

Итак, API на уровне пользователя:

// returns name of property with sequential number nProperty, or error
errno_t listproperties( int fd, int nProperty, char *buf, int buflen );

errno_t getproperty( int fd, const char *pName, char *buf, int buflen );
errno_t setproperty( int fd, const char *pName, const char *pValue );

Правила:

1. Никаких дефайнов с номерами, только имена.
2. Никаких бинарных данных, только строки

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

Так как мы с коллегами буквально на прошлой неделе завершили большой проект Web Dashboard'а (точнее — компонента, позволяющего создавать и просматривать ваши собственные дэшборды), в котором как раз стояла цель разработки удобного интерфейса, я решил осветить в статье, на какие основные моменты при проектировании интерфейса стоит обратить внимание, и привёл примеры нашего решения.

См. две другие статьи этой группы — Делаем многозадачность и Преемптивность: как отнять процессор.

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

Итак, в прошлых статьях описан механизм реализации многозадачности за вычетом планировщика, он же шедулер, он же скедулер, он же Васька меченый, сорри, заговариваюсь я с этими терминами…

Как я уже говорил, шедулер — это просто функция, которая отвечает на вопрос: какую нить и на сколько времени поставить на процессор.

Кстати, в SMP системе шедулер ничем не отличается от однопроцессорного. Вообще, чтобы проще понимать структуру взаимодействия сущностей на одном и нескольких процессорах, проще всего представить себе следующую модель: для каждого процессора есть нить «простоя» (которая работает, если вообще больше некому и просто останавливае процессор до прерывания), которая постоянно пытается «отдать» процессор (которым она как бы владеет) другим нитям, выбирая нить с помощью шедулера.

Говоря о шедулере нельзя не сказать о приоритетах.

Приоритет — свойство нити (или процесса) влияющее на конкуренцию этой нити с другими нитями за процессор.

Приоритет обычно описывается парой <класс приоритета, значение приоритета внутри класса>.

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

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

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

Но, как обычно, есть нюансы. См. код для интела.

Сам «отъём» процессора делается как в рамках обычного хардверного прерывания, обычно — по таймеру, так и в рамках «софтверного» прерывания — которое, собственно, такое же прерывание, но вызванное специальной инструкцией процессора. Такой способ переключения контекста нужен, если мы (например, в рамках примитива синхронизации) явно останавливаем нить и не хотим ждать, пока прилетит таймерное прерывание.

Я стараюсь чередовать статьи про разработку ОС вообще и специфические для ОС Фантом статьи. Эта статья — общего плана. Хотя, конечно, я буду давать примеры именно из кода Фантома.

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

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

Шедулер — это функция, которая отвечает на вопрос «какой нити отдать процессор прямо сейчас». Всё. Простейший шедулер просто перебирает все нити (но, конечно, готовые к исполнению, не остановленные) по кругу (RR алгоритм). Реальный шедулер учитывает приоритеты, поведение нити (интерактивные получают больше, чем вычислительные), аффинити (на каком процессоре нить работала в прошлый раз) и т.п., при этом умеет сочетать несколько классов приоритетов. Типично это класс реального времени (если есть хотя бы одна нить этого класса — работает она), класс разделения времени и класс idle (получает процессор только если два предыдущих класса пустые, то есть в них нет нитей, готовых к исполнению).

На сём пока про шедулер закончим.

Перейдём к собственно подсистеме, которая умеет отнять процессор у одной нити и отдать его другой.

Сервер очередей Gearman — прекрасный инструмент. Но в работе сервер очередей в чем-то напоминает системный блок: что-то делает, но для того чтобы знать, что именно, и управлять процессом, нужен монитор с клавиатурой, и представление о том, что вообще происходит в системном блоке.
Зачастую кажется, что Gearman — как диковинный инструмент без рукоятки: интересен и красив, но неясно, зачем нужен, а пользоваться болезненно.
Нужно выбраться из этой ситуации, Gearman действительно хорош.
Давайте рассмотрим:

• Gearman «на пальцах»
• примеры реальных задач с использованием Gearman
• веб-приложение и класс для мониторинга в реальном времени и управления процессами на сервере очередей Gearman

Интересно? Прошу под кат.

Ниже будет приведен список инструментов мониторинга. Есть как минимум 80 способов, с помощью которых ваша машинка будет под контролем.



1. первый инструмент — top

Консольная команда top- удобный системный монитор, простой в использовании, с помощью которой выводится список работающих в системе процессов, информации о этих процессах. Данная команда в реальном времени сортирует их по нагрузке на процессор, инструмент предустановлен во многих системах UNIX.

Elasticsearch — поисковый движок с json rest api, использующий Lucene и написанный на Java. Описание всех преимуществ этого движка доступно на официальном сайте. Далее по тексту будем называть Elasticsearch как ES.

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

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

Последняя статья про классические примитивы синхронизации.

(Наверное, потом напишу ещё одну про совсем уже нетипичную задачу, но это потом.)

Сегодня мы немножко заглянем в процессор. Чуть-чуть.

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

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

На уровне процесса всё так и есть — различия между спинлоком и мьютексом — чисто технические, вопрос реализации и производительности.

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

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

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

Итак, иерархия реализации такова: mutex/cond/sema сделаны на базе спинлоков, спинлоки — на базе атомарных операций, предоставляемых процессором. Мы в них немного заглянем сегодня.

Как устроен спинлок?

В прошлой заметке мы обсудили самую известную пару из лагеря инструментов синхронизации тредов — mutex и cond. Сегодня встретимся с sema — примитивом, который умеет заменять предыдущие два в одиночку.

Но сначала — пара слов о случайных пробуждениях. (Спасибо xaizek, который мне об этом напомнил.) В принципе, строго реализованные механизмы синхронизации этим не страдают, но, тем не менее, опытный программист на это никогда не полагается.

Напомню фрагмент кода:

while(total_free_mem <= 0)
    {
    wait_cond(&got_free_mem, &allocator_mutex);
    }

Здесь цикл вокруг wait_cond гарантирует нам, что даже если мы вернёмся из ожидания события случайно или по ошибке, ничего страшного не случится — проверка в while обеспечит нам уверенность, что нужное состояние проверяемого объекта достигнуто. Если нет — поспим ещё в ожидании.

Отметим ещё раз, что проверяем мы состояние объекта (total_free_mem <= 0) при запертом мьютексе, то есть никто не может его менять в то же самое время.

Когда я делаю ошибку в коде, то обычно это приводит к появлению сообщения “segmentation fault”, зачастую сокращённого до “segfault”. И тут же мои коллеги и руководство приходят ко мне: «Ха! У нас тут для тебя есть segfault для исправления!» — «Ну да, виноват», — обычно отвечаю я. Но многие ли из вас знают, что на самом деле означает ошибка “segmentation fault”?

Чтобы ответить на этот вопрос, нам нужно вернуться в далёкие 1960-е. Я хочу объяснить, как работает компьютер, а точнее — как в современных компьютерах осуществляется доступ к памяти. Это поможет понять, откуда же берётся это странное сообщение об ошибке.

Вся представленная ниже информация — основы компьютерной архитектуры. И без нужды я не буду сильно углубляться в эту область. Также я буду применять всем известную терминологию, так что мой пост будет понятен всем, кто не совсем на «вы» с вычислительной техникой. Если же вы захотите изучить вопрос работы с памятью подробнее, то можете обратиться к многочисленной доступной литературе. А заодно не забудьте покопаться в исходном коде ядра какой-нибудь ОС, например, Linux. Я не буду излагать здесь историю вычислительной техники, некоторые вещи не будут освещаться, а некоторые сильно упрощены.

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

Мы в 1cloud стараемся рассказывать о различных технологиях — например, контейнерах, SSL или флеш-памяти.

Сегодня мы продолжим тему памяти. Разработчик Роберт Элдер (Robert Elder) в своем блоге опубликовал материал с описанием возможностей виртуальной памяти, которые известны не всем инженерам. Мы представляем вашему вниманию основные мысли этой заметки.

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

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

Процессоры, используемые в наших продуктах — это, в основном, 16- и 32-битные микроконтроллеры Microchip, имеющие RAM от 8 до 32 кБ, и ROM от 128 до 512 кБ, без MMU. Иногда, для самых простых устройств, используются еще более скромные 8-битные чипы.

Очевидно, что у нас нет (разумных) шансов использовать ядро Linux. Так что нам нужна какая-нибудь RTOS (Real-Time Operating System). Находятся даже люди, которые не используют никаких ОС в микроконтроллерах, но я не считаю это хорошей практикой: если железо позволяет мне использовать ОС, я ее использую.

Несколько лет назад, когда мы переходили с 8-битников на более мощные 16-битные микроконтроллеры, мои коллеги, которые были гораздо более опытными, чем я, рекомендовали вытесняющюю RTOS TNKernel. Так что это — та ОС, которую я использовал в разных проектах в течение пары лет.

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