Ragel modes comparison

I have recently decided to create a parser of SMTP addresses (RFC 5321) in ragel. Therefore, I have implemented the basic grammar using it in rspamd: smtp_address.rl.

Ragel has three modes of code generation:

1. Table driven (T mode) - all states are pushed into one table and transitions are calculated using the next state and the input character performing states table lookup depending on the current state
2. Alphabet driven (F mode) - same as previous but states are searched using the current character as index
3. Goto driven mode - no tables are created but there are really many goto statements in the code

Initially, I thought that goto driven mode is not very friendly for the modern CPU. However, I decided to perform some performance tests. I've used the ragel generated code to parse 100K of email addresses all in the form of '<@domain1,@domain2:addr%d@example.com>'. Yes, this is a valid SMTP address (counting that %d is replaced with some number) and this enforces the most of state machine to be used.

Here are results from 30 measurements using -O0 optimization level:

And with heavy optimizations - -O3 -march=native 

Tests were performed on my macbook with Haswell CPU. Compiler - clang-3.8.

As you can see, T mode is the slowest and G mode is the winner. F mode has shown the intermediate results. However, the generated code size for G mode is the largest among these options and F mode is the winner in this case. On the other hand, F mode is not suitable for wide input alphabet mode.

How fast is your memchr

Recently, I got a simple task: calculate line counts in some text. The trick was to do it as quickly as possible. The naive approach was just to use some cycle on a text and count all characters whose code is '\n'. But of course this approach is not very clever.

The second approach was to take the standard memchr function from the C library. This is the most portable but not equally effective approach on different platforms.

The third approach was to treat input as a sequence of 32 or 64 bit integers and use 'XOR' operation with the repeated pattern. However, the trick was to use special magic bits to track if some of bytes in this word are zero after 'XOR'. The idea was taken from GNU C library, where it is used in memchr function.

The code that evaluates the performance of each method is placed here:
https://gist.github.com/vstakhov/99c04d6aa18e47c7950d

Currently, it uses linux specific timer to get time intervals, so if you want to test it on your OS then you need to change this timer's value appropriately.

Here are some results:

Linux/amd64 (gcc 4.8 -O3)

Naive: 5583 0.001655
Stupid xor: 5583 0.001553
Memchr: 5583 0.000229
Magic bits: 5583 0.000352

Here we can see that memchr in glibc is blazingly fast.

FreeBSD/amd64 (clang 3.4.1 -O3)

Naive: 5589 0.001343
Stupid xor: 5589 0.001431
Memchr: 5589 0.001323
Magic bits: 5589 0.000444

In FreeBSD, memchr is almost as slow as naive implementation.

Solaris/amd64 (gcc 4.4 -O2) - this is another hardware platform and test

Naive: 9013 0.872925
Stupid xor: 9013 0.812501
Memchr: 9013 0.889934
Magic bits: 9013 0.955014

-m64 -O2

Naive: 9013 1.138129
Stupid xor: 9013 0.982253
Memchr: 9013 0.741068
Magic bits: 9013 0.349103


As we can see, in Solaris, memchr is reasonably fast but is almost twice slower than bithack approach when used in 64 bits mode.

UPDATE: I've added some more cases to the evaluation, namely SSE2 and AVX2 versions using compiler intrinsics. Finally, I've evaluated the performance of algorithms on a larger file using my Mac laptop with Haswell CPU:

-m64 -mavx2 -O2

Naive: 4471200 0.179973
Stupid xor: 4471200 0.186705
Memchr: 4471200 0.083217
Memchr (musl): 4471200 0.164340
Magic bits: 4471200 0.122103
SSE: 4471200 0.073190
AVX2: 4471200 0.06790

So OSX libc is fast enough to beat the bithack version, so I presume it uses SSE for speed. Nonetheless, in 32 bits mode it sucks (but naive version comes even faster than libc one, because clang is smart enough to optimize it using SSE instructions):

-m32 -mavx2 -O2

Naive: 4471200 0.123135
Stupid xor: 4471200 0.109367
Memchr: 4471200 0.313270
Memchr (musl): 4471200 0.336193
Magic bits: 4471200 0.223416
SSE: 4471200 0.071051
AVX2: 4471200 0.070952

The performance of avx2 and sse2 versions is almost the same in this case. I've found that the version with vmovntdqa was slightly slower than a version with vpmaskmovd.

How to find running statements in sqlite3

Quite often, sqlite3 users get SQLITE_LOCKED error code when trying to execute some query. Sometimes it is related to concurrent access and is well documented here. However, in case of DROP TABLE operation it is practically useless. I have used the following method to detect which statements are not finished yet. To use it, you need some debugger that can attach to a running process. Then you need to set a breakpoint just near sqlite3_exec or whatever other function that causes SQLITE_LOCKED. Then, you need to step inside that function and print the database object (and you need sqlite3 debug symbols + source code to do these checks):

(lldb) p *db

...
nVdbeActive = 1
nVdbeRead = 1

So you have a single unfinished query. But to find it we need to apply some sort of black magic. First of all, sqlite stores statements that are not finalized (e.g. prepared statements) inside db object in a linked list of Vdbe* structures. Each Vdbe structure contains a single statement (actually, sqlite3_stmt is an opaque name for Vdbe structure). But how could we find, which query is finished and which is active. Here is the code from sqlite3 itself:

SQLITE_API int sqlite3_stmt_busy(sqlite3_stmt *pStmt){
  Vdbe *v = (Vdbe*)pStmt;
  return v!=0 && v->pc>0 && v->magic==VDBE_MAGIC_RUN;
}

Hence, we need to check 2 fields of Vdbe structure: pc (program count) and magic. In decimal form magic for active statements is 3186757027. The subsequent operations are quite simple: iterate over linked list (by using pNext field or by writing some macro to simplify this procedure) and find queries, that have pc > 0 and magic equal to 3186757027:

(lldb) p *db->pVdbe->pNext->pNext->pNext->pNext->pNext->pNext->pNext
zSql = 0x0000000801067c08 "SELECT version FROM packages WHERE origin=?1"
magic = 3186757027
pc = 12

Finally, examine and fix your code to reset that statement prior to calling for DROP TABLE/INDEX.

AIO в Linux.

Введение.

Не так давно я реализовывал систему асинхронного io для эффективной работы в Linux. Данный пост является компиляцией моего опыта в данной теме и описывает, в основном, ядерный io (который осуществляется через io_submit). Желающих ознакомиться с данным опытом прошу под кат.

Особенности флагов оптимизации gcc в ubuntu.

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

/tmp/cc3z0FbU.o: In function `main':
sgio.c:(.text.startup+0x248): undefined reference to `__printf_chk'
sgio.c:(.text.startup+0x25e): undefined reference to `__printf_chk'

В мануале об этом написано так:
NOTE: In Ubuntu 8.10 and later versions, -D_FORTIFY_SOURCE=2 is set by default, and is activated when -O is set to 2 or higher. This enables
additional compile-time and run-time checks for several libc functions. To disable, specify either -U_FORTIFY_SOURCE or -D_FORTIFY_SOURCE=0.

При следовании этим рекомендациям, проблема исчезает, однако, эта "фича" далеко не так очевидна.

VirtualBox OSE и PXE

Чтобы в VirtualBox OSE работал pxeboot в guest системах, надо загрузить и установить в настройках расширение Oracle VM VirtualBox Extension Pack. Найти можно тут.

Обзор rspamd

Планировал разместить эту статью на хабре, но, к сожалению, по каким-то причинам она не прошла премодерации в "песочнице". Поэтому продублирую ее здесь.

Автообучение rspamd

Стало совершенно очевидным, что автообучение, основанное на срабатывании правил, как это сделано в SA, - совершенно порочная практика, которая реально может привести к тому, что хорошие письма, но отправленные "не с тех" релеев или же имеющие некоторые спам сигнатуры (а таких честных писем достаточно много), будут статистикой еще больше давиться в сторону оценки как спам. Кроме того, это может засорять статистику неправильными срабатываниями. Для rspamd сейчас я продумываю концепцию, чтобы сделать автообучение максимально адаптивным.

Мысли о конфигурационных файлах.

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

Отчет о поездке в Киров на машине

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

Цвета подсказок eclipse в ubuntu.

При запуске eclipse под ubuntu подсказки отображаются черными на черном. Решения этой проблемы подробно рассмотрены тут:
https://bugs.launchpad.net/ubuntu/+source/light-themes/+bug/540332

Для себя я  выбрал способ добавления в ini файл опций раскраски:



При этом, если какой-то плагин продолжает показывать корявые цвета, то его настройки можно найти в той же директории и таким же образом похачить. Например, так я починил плагин ShellEd (net.sourceforge.shelled.ui.prefs).

BSD diff

Исправляя проблему в rspamd с неверным рассчетом "похожести" частей в мультипарте, решил заменить вычисление расстояния Левенштейна на поиск максимальной общей подстроки - алгоритм, используемый в diff. В итоге нашел алгоритм под MIT лицензией (практически аналогичной BSD), который мне и подошел: http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
После небольших изменений под glib (например, использование GArray) я написал тест для сравнения с вычислением расстояния Левенштейна. Для коротких текстов разница в скорости практически незначительна, но уже на 20кб тексте расстояние Левенштейна считалось 8 секунд, а diff алгоритм выполнился за 8 миллисекунд, что вполне приемлимо для работы.
Теперь пытаюсь найти алгоритм для вычисления нечеткой сигнатуры для письма. Используемый сейчас алгоритм - производная от ssdeep - очень плохо устойчив к сдвигам внутри текста. Любой сдвиг гарантированно разбивает несколько участков сигнатуры. Кроме этого, есть задача сокращения размерности сигнатуры (сейчас это 64 символа) для того, чтобы искать сигнатуру по KD-дереву, которое опять же плохо работает для больших размерностей (неэффективно как в плане памяти, так и в плане нахождения похожих элементов).

Новый переезд

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

Обсчет данных ip accounting по заданному ip

Возникла задача разбирать логи ip accounting'а с целью определить, какой пользователь куда тратит свой трафик. Для этой цели написал простой перловый скрипт, который разбирает строчки данных ip accounting'а, ищет строчки, относящиеся к заданному ip и выводит 2 списка: общий список адресов исходящего и входящего трафика, и список 5-ти самых активных адресов. Возможно, кому-то пригодится. Лежит тут: http://cebka.pp.ru/stuff/ipacct_counter.pl. Пример использования:

# cat /data/log/ipacct/2010-05-25/2010-05-25-00 | perl ipacct_by_dest.pl <ip>

Bitbucket.org

В связи с многочисленными проблемами работы с sourceforge, связанных, например, с невозможностью управления trac'ом, я решил, что лучше будет перенести публичный репозиторий на http://bitbucket.org. Это платформа для публикации кода, где все элементы помещаются в mercurial репозитории (например, wiki). Это делает очень удобным резервное копирование информации. Так что http://rspamd.sourceforge.net сейчас редиректит на bitbucket. Также я практически дописал основную документацию к rspamd, и теперь она доступна в том числе в wiki butbucket'а. Для конвертации из texinfo, который я использую для написания документации, в wiki формат (creole - http://www.wikicreole.org/) я написал небольшой скрипт на перле, который конвертирует основные элементы документации (лежит тут: http://cebka.pp.ru/stuff/info2wiki.pl). Разумеется, он конвертирует неполный набор тегов docbook и зачастую работает не совсем верно, но, насколько я знаю, это единственный способ конвертации, т.к. варианты texinfo->docbook->wiki также не реализованы нормально. Кроме этого, я, наконец, затегал 0.3.0. В планах к 0.3.1 написание smtp прокси для обработки спама на ранних стадиях, а также допиливание документации к lua API rspamd.

Ng_multicar или шейпинг трафика для большого числа ip адресов

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

/* Look up hook by name */
hook_p
ng_ipfw_findhook(node_p node, const char *name)
{
        u_int16_t n;    /* numeric representation of hook */
        char *endptr;

        n = (u_int16_t)strtol(name, &endptr, 10);
        if (*endptr != '\0')
                return NULL;
        return ng_ipfw_findhook1(node, n);
}

/* Look up hook by rule number */
static hook_p
ng_ipfw_findhook1(node_p node, u_int16_t rulenum)
{
        hook_p  hook;
        hpriv_p hpriv;

        LIST_FOREACH(hook, &node->nd_hooks, hk_hooks) {
                hpriv = NG_HOOK_PRIVATE(hook);
                if (NG_HOOK_IS_VALID(hook) && (hpriv->rulenum == rulenum))
                        return (hook);
        }

        return (NULL);
}

Кроме этого, такое использование ng_car подходит только для ipfw с его ng_ipfw. В моем случае для pf'а необходимо направлять весь трафик в netgraph ноду (например, с ng_ether), поэтому задача разделения полос и ip адресов возлагается целиком на netgraph модуль. Возникли следующие идеи по реализации такого шейпера:

• Использовать для хранения информации о полосе для ip judy массив для ускорения поиска


• Для загрузки и выгрузки информации о полосах и соответствующих им ip использовать либо отдельные команды, либо парсить некоторый загрузочный файл



• Поддерживать создание динамических полос для сетей, например, если аргумент - сеть в CIDR формате, то создавать полосу для ip по получению пакета от данного ip из данной сети (нечто вроде динамических пайпов dummynet'а)

При такой схеме при увеличении числа пользователей нагрузка на роутер не должна значительно возрастать.

OpenID и wordpress

Плагин для работы openid аутентификации в wordpress работает достаточно странно: он требует для парсинга XRDS xml парсер, но то, как он пытается его загрузить, довольно ужасно:

        if (!extension_loaded($name)) {
            foreach ($params['libname'] as $libname) {
                if (@dl($libname)) {
                    $classname = $params['classname'];
                }   
            }   
        } else {

То есть, при отсутствии заданного расширения, он пытается его dlopen'уть, но при этом игнорируя любые ошибки. В итоге ошибка dl становится фатальной, но нигде не отображается. Опытным путем выяснилось, что для работы плагина необходимо расширение dom.so (textproc/php5-dom). Сейчас openid авторизация тут должна работать.

Rspamd и xml

Замучавшись бороться с lex+yacc решил перевести конфигурацию rspamd в xml формат. Минусы старой системы довольно прозаичны: lex при переключении внутренних состояний парсера (lex states) не умеет при yyrestart'е переключаться в INITIAL state, что приводит к невозможности перечитывания конфига "на лету". Кроме этого, сами по себе lex+yacc предоставляют слишком много возможностей для генерации грамматик, что само по себе неплохо, но я ловлю себя на мысле, что bind like конфиг-файл зачастую не очень очевиден для пользователя, яркий пример, когда переменные rspamd на самом деле являются не переменными в полном понимании этого слова, а подстановками текста. Также такой конфиг крайне сложно парсить чем-то, отличным от оригинальной lex/yacc грамматики. Моя же идея была в расширении интерфейса управления кластера rspamd, давая возможность конфигурации машин в кластере более-менее атоматически. Выбор лежал между ini-like форматом и xml (yaml и json тоже рассматривались, но никаких существенных преимуществ, кроме уменьшения размера конфига, я не нашел), но у ini нет понятия уровней вложенности, а это мне было нужно для описания файлов статистики внутри classifier'а. Конечным решением системы, которая бы предоставляла компромисс между удобством ручного написания сложных правил и возможностью настройки параметров автоматически (через web интерфейс или же shell script), я выбрал lua + xml. То есть, логика правил описывается в lua, используя все возможности этого языка, включая, например, переменные, являющиеся функциями, а включаются эти правила, а также назначаются веса, описываются рабочие процессы в xml. Такое решение, на мой взгляд, позволяет отделить код правил от собственно процесса настройки системы. Поддержку старого формата я оставил, и теперь rspamd умеет конвертировать старый формат в xml (конвертировать правила в lua он, к сожалению, не умеет, но умеет представлять их в виде xml). Сразу же видимый профит - возможность "мягкого" рестарта с перечитыванием конфига. В будущем планируется введение динамических правил, которые можно было бы загружать в кластер через контроллер, не выполняя рестарта. Также анализ правил, заимствованных из spamassassin'а показал, что все это лучше делать через отдельные статистические файлы, которые после обучения поставлять вместе с rspamd. Ну и напоследок, если у кого-то вдруг появилось желание заменить SA или другую систему спам фильтрации на rspamd, но в rspamd не хватает какой-то функциональности, то я был бы рад выслушать подобные замечания, равно как и другие идеи по развитию проекта.

Небольшой обзор возможностей rspamd

Так как до сих пор у меня не появилось идей, как рассказать легко и понятно о том, зачем и как использовать rspamd, я написал краткий обзор rspamd: фичи, установка, настройка и обучение. Надеюсь, он будет полезен тем, кто хочет использовать rspamd или тем, кто даже не знает о его существовании. Обзор тут:  http://cebka.pp.ru/why-rspamd.html.

ICQ транспорт и kqueue

При настройке icq транспорта (разумеется, имеется в виду py-icqt, так как остальные существующие сейчас проекты либо мертвы, как jit, либо не работают) на FreeBSD возникло странное желание использовать kqueue reactor, так как очевидно, что традиционные select/poll - не лучший выбор при сколько-нибудь большом числе persistent коннекций. Итак, вначале необходимо поставить devel/py-kqueue. Далее, если мы пропишем в конфигурационном файле

<reactor>kqueue</reactor>

то, скорее всего pyicqt начнет кушать 100% CPU. Если посмотреть ktrace, то можно будет увидеть следующее:

25821 python2.5 RET   kevent -1 errno 9 Bad file descriptor
25821 python2.5 CALL  gettimeofday(0xbfbfd8c8,0)
25821 python2.5 RET   gettimeofday 0
25821 python2.5 CALL  gettimeofday(0xbfbfd5b8,0)
25821 python2.5 RET   gettimeofday 0
25821 python2.5 CALL  write(0x2,0x28e70014,0x2ab)
25821 python2.5 GIO   fd 2 wrote 683 bytes
"Traceback (most recent call last):
File "/usr/local/lib/jabber/pyicq/PyICQt.py", line 16, in <module>
main.main()
File "/usr/local/lib/jabber/pyicq/src/main.py", line 473, in main
reactor.run()
File "/usr/local/lib/python2.5/site-packages/twisted/internet/base.py", line 1128, in run
self.mainLoop()
--- <exception caught here> ---
File "/usr/local/lib/python2.5/site-packages/twisted/internet/base.py", line 1140, in mainLoop
self.doIteration(t)
File "/usr/local/lib/python2.5/site-packages/twisted/internet/kqreactor.py", line 189, in doKEvent
l = self._kq.kevent([], len(self._selectables), timeout)
exceptions.OSError: [Errno 9] Bad file descriptor
"
Вспоминаем неприятную особенность kqueue: при форке не наследуюся kqueue дескрипторы. То есть, необходимо выполнить демонизацию самостоятельно. Вторая проблема - неверный расчет тайм-аутов. Фикс ее:

--- kqsyscallmodule.c.bak    2009-10-02 18:24:37.000000000 +0400
+++ kqsyscallmodule.c    2009-10-02 18:26:37.000000000 +0400
@@ -141,7 +141,7 @@
}

statichere PyTypeObject KQEvent_Type = {
-  PyObject_HEAD_INIT(NULL)
+  PyObject_HEAD_INIT(&PyType_Type)
0,                             // ob_size
"KQEvent",                     // tp_name
sizeof(KQEventObject),         // tp_basicsize
@@ -295,14 +295,14 @@

/* Build timespec for timeout */
totimespec.tv_sec = timeout / 1000;
-  totimespec.tv_nsec = (timeout % 1000) * 100000;
+  totimespec.tv_nsec = (timeout % 1000) * 1000000;

// printf("timespec: sec=%d nsec=%d\n", totimespec.tv_sec, totimespec.tv_nsec);

/* Make the call */
-
+  Py_BEGIN_ALLOW_THREADS
gotNumEvents = kevent (self->fd, changelist, haveNumEvents, triggered, wantNumEvents, &totimespec);
-
+  Py_END_ALLOW_THREADS
/* Don't need the input event list anymore, so get rid of it */
free (changelist);

@@ -365,7 +365,7 @@
statichere PyTypeObject KQueue_Type = {
/* The ob_type field must be initialized in the module init function
* to be portable to Windows without using C++. */
-    PyObject_HEAD_INIT(NULL)
+    PyObject_HEAD_INIT(&PyType_Type)
0,            /*ob_size*/
"KQueue",            /*tp_name*/
sizeof(KQueueObject),    /*tp_basicsize*/

Очевидно, что для получения наносекунд, нужно умножить миллисекунды на миллион, а не на сто тысяч.

Вторая проблема - корявая демонизация. Я решил ее исправлением стартового скрипта следующим образом:

--- /usr/local/etc/rc.d/jabber-pyicq-transport.orig    2009-10-02 18:57:06.000000000 +0400
+++ /usr/local/etc/rc.d/jabber-pyicq-transport    2009-10-02 19:29:00.000000000 +0400
@@ -24,8 +24,9 @@
: ${jabber_pyicq_user="ejabberd"}

pidfile="${jabber_pyicq_piddir}/PyICQt.pid"
-command_interpreter="/usr/local/bin/python2.5"
-command="${jabber_pyicq_dir}/PyICQt.py"
-command_args="-b -o pid=${pidfile}"
+python="/usr/local/bin/python2.5"
+procname="${python}"
+command="/usr/sbin/daemon"
+command_args="${python} ${jabber_pyicq_dir}/PyICQt.py -o pid=${pidfile}"

run_rc_command "$1"

То есть, демонизация происходит при помощи /usr/sbin/daemon. Проверка трейса работы pyicqt показала, что после этих действий для работы он использует kevent, причем, использует правильно. Хотя наличие select'ов все равно смущает, но для socket IO он все же использует kqueue.