JITиё моё

Этот пост посвящаю хорошему человеку и хорошему программисту — Ярославу, недавно реализовавшему свой первый Brainfuck-интерпретатор.

Итак, все мы любим компиляторы и виртуальные машины. Некоторые из них считаются круче, потому что в них есть JIT. А что же такое этот JIT?

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

А как это работает внутри? Вот об этом и поговорим.

Brainэтосамое

Итак, напишем свой JIT компилятор для Самого Простого Языка. Сложнее языки я не потяну, да и лень, а еще проще… Ну проще просто не бывает.

Дано. Инструкции <, > = сдвинуть указатель влево-вправо; +, — = увеличить/уменшить на 1 значение по указателю, [ и ] — начало и конец цикла (в цикл входим если значение по указателю не равно нулю). Еще есть точка и запятая — для ввода и вывода символов.

Простой не-JIT интерпретатор пишется легко (хотя и погружает вас в мистический мир виртуальных машин и всего такого):

char m[9999],*n[99],*r=m,*p=m+5000,**s=n,d,c;main(){for(read(0,r,p)
;c=*r++;c-93?c-91?d?0:c-43&~2?c-44?c-46?p+=c&~2^60?0:c%4-1:write(1,
p,1):read(2,p,1):(*p-=c-44):d++||(*++s=r):d&&--d?0:*p?r=*s:--s);}

Ой. Я этот код украл в образовательных целях (http://esoteric.sange.fi/brainfuck/impl/interp/small.c). Ну, если совсем не понятно — вот код интерпретатора на самом брейнф-е:

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]

Это код из http://www.hevanet.com/cristofd/brainfuck/
Вроде бы это самый лаконичный.

Но, давайте делать JIT.

JIT

И вот оно разочарование. Нет никакой магии. Просто выделяем сегмент памяти (с правами rwx, чтобы код в нем можно было читать, писать и выполнять), пишем туда куски машинного кода, и делаем туда goto. Всё. Потом освобождаем память. Делать в настоящей жизни такое на каждый чих не нужно, наверное нужно оптимизировать только часто выполняемые участки кода, длинные циклы и все такое. Да, тут уже конечно без магии никуда. Но мы сейчас не об этом. Итак, простой JIT.

Сколько машинных инструкций вы помните наизусть? Вот и я ни одной. Поэтому предлагаю такой вот хак. Например для инструкции «+» (которая «(*p)++» в С) делать следующее:

bf_inc_start:
  (*p)++;
bf_inc_end:

Теперь, у нас есть адрес начала машинного кода и его конца. Можно делать memcpy(). Чтобы не писать все руками сделаем пару макросов:

#define JIT_BEGIN(name) bf_ ## name ## _begin
#define JIT_END(name) bf_ ## name ## _end
#define nop() asm ("nop");

#define JIT_CODE(name, code) \
	if (jit == 0) { \
		JIT_BEGIN(name): \
		code ; \
		JIT_END(name): \
		nop(); \
	} else { \
		memcpy(jitptr, &&JIT_BEGIN(name), \
				&&JIT_END(name) - &&JIT_BEGIN(name)); \
		jitptr += &&JIT_END(name) - &&JIT_BEGIN(name); \
	}

Эти макросы очень некрасивые, но работают. JIT_CODE либо интерпретирует код, либо копирует соответствующие машинные инструкции в область памяти для JIT. Кстати, без nop() вы рискуете узнать, что метки в конце блоков кода не ставят, напр.:

if (...) {
  ...
label: /* так нельзя */
}

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

void bf(const char *s, int jit) {
	volatile char mem[8];
	volatile char volatile *p = mem;
	volatile void  *loops[128]; /* who needs more than 128 nested loops in BF?! */
	volatile void **sp = loops;
	volatile void *jitend;
	void *code;
	void *jitptr;
	int (*in)(void) = &getchar;
	int (*out)(int)  = &putchar;
	int i;

	int sz = 4096;

	memset(mem, 0, sizeof(mem));

	if (jit) {
		code = mmap (0, sz, PROT_READ | PROT_WRITE | PROT_EXEC,  
				MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
		jitptr = code;
	}
	for (;;) {
		switch (*s++) {
			case '<':
				JIT_CODE(left, p--);
				break;
			case '>':
				JIT_CODE(right, p++);
				break;
			case '+':
				JIT_CODE(inc, (*p)++);
				break;
			case '-':
				JIT_CODE(dec, (*p)--);
				break;
			case ',':
				JIT_CODE(in, (*p) = in());
				break;
			case '.':
				JIT_CODE(out, out((int) *p));
				break;
			case '[':
				if (jit) {
					*sp++ = jitptr;
					JIT_CODE(enter, { if (*p == 0) { void *endloop = 0x0123456789abcdef; goto *endloop; }});
				} else {

				}
				break;
			case ']':
				if (jit) {
					void *start = *(--sp);
					void *patchhi, *patchlo;
					uint32_t patternhi = 0x01234567;
					uint32_t patternlo = 0x89abcdef;
					patchhi = xmemmem(start, jitptr - start, &patternhi, sizeof(patternhi));
					patchlo = xmemmem(start, jitptr - start, &patternlo, sizeof(patternlo));
					JIT_CODE(exit, { asm volatile("jmp *%0" :: "r" (start)); })
					(* ((uint32_t *) patchhi)) = (uint32_t) ((uintptr_t) jitptr >> 32);
					(* ((uint32_t *) patchlo)) = (uint32_t) ((uintptr_t) jitptr & 0xffffffff);
				} else {

				}
				break;
			case '\0':
				if (!jit) {
					return;
				}
				JIT_CODE(ret, asm volatile("jmp *%0" :: "r" (&&end)));
				goto do_jit;
		}
	}
do_jit:
	if (jit) {
		unsigned char *p;
		memcpy(jitptr, &&JIT_BEGIN(ret), &&JIT_END(ret) - &&JIT_BEGIN(ret));
		jitptr += &&JIT_END(ret) - &&JIT_BEGIN(ret);

		for (p = code; p < jitptr; p++) {
			printf("%02x ", *p);
		}
		printf("\n");
		goto *code;
	}
end:
	if (jit) {
		munmap(code, sz);
	}
	printf("POINTER=%ld\n", p - mem);
	for (i = 0; i < sizeof(mem); i++) {
		printf("%02x ", (unsigned char) mem[i]);
	}
	printf("\n");
	return;
}

Переменная «jit» определяет режим — интерпретатор или компилятор JIT. Все переменные связанные с состоянием BF-машины делаем volatile, чтобы оптимизатору неповадно было.
С помощью mmap/munmap работаем с областью памяти для JIT.

Как в любом интерпретаторе BF в цикле читаем инструкции. Для каждой их них либо формируем машинные инструкции, либо интерпретируем (макрос JIT_CODE).

» заслуживает отдельной обработки, т.к. он возвращает нас назад в нашу функцию из JIT-области.

После всех операций и компиляции, если мы в JIT-режиме — дописываем «ret» и делаем goto в скомпилированную область. Если не рухнем — то все удачно.

В конце работы просто показываем чё наш язык наделал — состояние памяти и указателя.

А что же с циклами? На открывающую скобку запоминаем текущий адрес в JIT-области, нам сюда еще возвращаться. Код JIT такой — если под указателем сейчас 0 — прыгнуть в конец цикла. А где конец цикла? Пока не знаем. Заменяем этот адрес на метку — 0x0123456789abcdef (у меня 64-битная система). Когда встречаем закрывающую скобку — берем адрес открывающей из стека, делаем туда jmp. И патчим нашу метку фактическим адресом конца цикла.

Кстати, у меня сломался memmem из glibc — пришлось писать свой. Я так понимаю эта функция вообще тяжелой судьбы (см. маны)?

Вот и всё. Запускаем:

bf("+++", 0) - интерпретируем. Получаем [3, 0, ....] в памяти
bf("+++", 1) - то же, но с JIT. 
bf("+[,.]", 1) - программа "cat" с JIT.
bf("+++[,.]", 1) - считывает три буквы
На hello world - падает 🙂

Вообщем, так JIT писать нельзя. Работает только с gcc без оптимизаций, на 32-битной системе немного проще и стабильнее (как переделать под 32 бита — домашнее задание). Хотя идея конечно вначале казалась забавной — использовать машинный код одного компилятора для другого да еще и убить двух зайцев. Авантюра не удалась.

Выводы

Можно делать JIT по-человечески. Есть библиотечка GNU lightning (http://www.gnu.org/software/lightning/) для генерации JIT-кода, она дает более-менее универсальный набор инструкций, и не глючит. Еще можно смотреть в сторону LLVM. Но, конечно, свой велосипед ближе к телу.

Реклама

Регулярные выражения и выражения благодарности Робу Пайку.

Я думаю все слышали про регулярные выражения и знают зачем они нужны — по сути они позволяют узнать соответствует ли строка регулярному выражению, и если да — то какие именно участки строки соответствуют каким участкам выражения.

А что если написать свой движок регулярных выражений?

Итак, вспомним, что регулярные выражения — это по сути конечный автомат. Когда мы встречаем какой-то символ — автомат переходит в новое состояние (если это возможно). Например, для выражения ab(cd|ef)g получится такой автомат:

RegEx State Automata

Я не буду вдаваться в подробности о детерминированных и недетерминированных автоматах. Просто будем помнить, что само выражение описывает всевозможные состояния и связи между ними, а входная строка буква за буквой переключает состояния автомата. Здесь, например, в состоянии 2 если на вход поступит буква ‘d’ — перейдем в состояние 3, если буква ‘c’ — в состояние 4. Иногда нельзя будет сказать в какое состояние переходить не заглядывая наперёд строки.

Самый простой движок регулярных выражений

Существует великолепная книжка Роба Пайка и (кажется) Брайна Кернигана — The Practice Of Programming (TPOP). Там приводится код простейшего движка для регулярных выражений. Кому лень читать всю книгу — тут описан основной подход и приводятся те самые легендарные 30 строк кода.

Движок способен распознавать начало/конец строки и задавать wildcard — маску для множества одинаковых символов.
Гениальность этой реализации в рекурсивном подходе. Код получается очень лаконичный, а разница в скорости почти не заметна.

Извлекаем больше пользы

Я решил использовать этот код за основу, но получить чуть больше, а именно:

  • Узнавать где начинается соответствие и сколько символов строки попадает под выражение
  • Добавить специальные группы символом — ну хотя бы \d для цифр и \s для пробелов
  • Добавить квантификаторы (ну или как это назвать?) для нахождения 0 и больше вхождений («*»), 1 и больше («+»), 0 или 1 («?») и жадного оператора для 0 и больше («-» — как в Lua)

Попробуем вложиться строчек эдак в 100.

Начинать будем так же — нам нужная единственная главная функция и функция, определяющая соответствие начала строки выражению — regex_match и regex_match_here соответственно:

int regex_match(const char *regex, char *s, int *len) {
	char *p = s;

	/* force match from the beginning of the string */
	if (regex[0] == '^') {
		return (regex_match_here(regex + 1, s, len) ? 0 : -1);
	}

	/* iterate the string to find matching position */
	do {
		*len = 0;
		if (regex_match_here(regex, p, len)) {
			return p - s;
		}
	} while (*p++ != '\0');

	return -1;
}

int regex_match_here(const char *regex, char *s, int *len) {
	// TODO
}

С regex_match все ясно, если «^» — проверяем начало строки, иначе — пляшем слева направо пока не найдем соответствие.

Самое главное находится в regex_match_here:

static int regex_match_here(const char *regex, char *s, int *len) {
	int c = regex[0];

	if (regex[0] == '\0') { /* end of regex = full match */
		return 1;
	} else if (regex[0] == '$' && regex[1] == '\0') { /* check end of string */
		return (*s == '\0');
	} else if (regex[0] == '\\' && regex[1] != '\0') { /* check escaped symbol */
		c = regex[1];
		if (c != '^' && c != '$' && c != '\\' && c != '+' && c != '*' && c != '-' && c != '?') {
			c = c | 0x100;
		}
		regex = regex + 1;
	}
	/* check for special operators *,+,?,- */
	if (regex[1] == '*' || regex[1] == '+' || regex[1] == '-' || regex[1] == '?') {
		return regex_match_quantity(regex[1], c, regex+2, s, len);
	} else if (*s != '\0' && regex_match_group(*s, c)) {
		*len = *len + 1;
		return regex_match_here(regex+1, s+1, len);
	}
	return 0;
}

Здесь проверяем состояние нашего неявного автомата:

  • если выражение закончилось (достигнуто конечное состояние) — вернуть 1, соответствие найдено
  • если в регулярном выражении дошли до последнего символа, и это — «$» (т.е. конец строки) — вернуть 1 если строка тоже закончилась.
  • если нашли «\» — экранирующий символ, но мы имеем дело с особой группой символов. Вообще, в обычном синтаксисе «\» играет две роли — для «\.», «\^», «\$», ‘\?’, ‘\*’, ‘\+’, ‘\-‘ он означает использовать просто символы «.», «^» и т.д. вместо из мета-значений («любой символ», «начало строки», «конец строки», …). Для остальных («\d», «\s», …) он означает использовать мета-значение («любая цифра», «любой пробельный символ», …). Договоримся, что значение выше 256 будут означать мета-символ, т.е. (‘d’|0x100) — это «любая цифра», а ‘d’ — буква ‘d’. Ах да, с точной («.») все будет наоборот. Ну и синтаксис.
  • итак, символ или группу мы считали. Теперь проверяем операторы «+», «*», «?» и «-«. Для них — особая функция проверки regex_match_quantity, а в остальных случаях — просто проверяем попадает ли следующий символ строки в группу и идёт дальше (рекурсивно).

Функция проверки попадания символа в группу простая и легко расширяемая:

static int regex_match_group(int c, int group) {
	if ((group & 0xff) == '.') group ^= 0x100;
	if (group < 0x100) { /* a single char */
		return c == group;
	}
	/* a meta char, like \d, ... */
	switch (group & 0xff) {
		case 'd': return isdigit(c);
		case 's': return isspace(c);
		case 'D': return !isdigit(c);
		case 'S': return !isspace(c);
		case '.': return 1;
	}
	return 0;
}

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

Ну и самый кошмарный код в функции regex_match_quantity:

static int regex_match_quantity(int quant, int c, const char *regex, char *s, int *len) {
	if (quant == '?') {
		if (regex_match_group(*s, c)) {
			*len = *len + 1;
			s = s + 1;
		}
		return regex_match_here(regex, s, len);
	}

	if (quant == '+' || quant == '*') { /* match as much as possible */
		char *p;
		for (p = s; *p != '\0' && regex_match_group(*p, c); p++) {
			*len = *len + 1;
		}
		if (quant == '+' && p == s) {
			return 0;
		}
		do {
			if (regex_match_here(regex, p, len)) {
				return 1;
			}
			*len = *len - 1;
		} while (p-- > s);
	} else if (quant == '-') { /* match as little as possible */
		do {
			if (regex_match_here(regex, s, len)) {
				return 1;
			}
			*len = *len + 1;
		} while (*s != '\0' && regex_match_group(*s++, c));
	}
	return 0;
}

Ну для «?» всегда возвращаем 1, но если символ действительно входит в группу — увеличиваем длину совпадающего региона на 1.

Для жадных операторов «+» и «*», которые захватывают как можно больше символов строки — так и поступаем. Проверяем сколько вообще символов строки может попасть в заданную группу, а затем возвращаемся назад пока не найдем соответствие остатка строки остатку регулярного выражения. Для «+» хотя бы один символ строки должен попасть в группу.

Для нежадного оператора «-» просто идёт слева направо пока не совпадет остаток строки с остатком выражения.

Вот и все. У меня получилось 98 строк. Ни одной зависимости. Из libc — только ctype.h, т.е. при особом умении соберется даже каким-нибудь ущербным SmallC. Также никаких особых плюшек С я не использовал, код должен быть переносим и на другие языки, на тот же Forth.

Весь код — как всегда на bitbucket.
Там же и горстка тестов чтобы быть уверенным что все работает как надо.

Вместо выводов

Спасибо Робу Пайку за элегантный и полезный код. Я понимаю, что для серьезных задач такие микро-регекспы не годятся, но для чего-нибудь простенького в embedded — вполне. Тем более лично я считаю, что не стоит делать и регулярных выражений тьюирнг-полный мега-язык, уж лучше бы был способ комбинирования простых регулярных выражений с примесью некоторой простой логики типа условний-циклов.

Здесь кстати тоже стоит отметить работу Роба Пайка о структурных регулярных выражениях. И его текстовый редактор Sam красочный пример их простоты и мощности. Спасибо, Роб.

P.S. Отдельно спасибо, Роб, за язык Go 🙂

О самодельном printf для идиотов, перегрузке функций в C и макросах

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

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

Стив Возняк. Где мои 16 лет. Велосипеды.

Я так понимаю, каждый уважающий себя айтишник должен придумать свой собственный процессор. Ну вы только посмотрите что творится вокруг DCPU-16. Ну Нотч, ну игра, ну процессор. А что такого особенного в этом DCPU16? По-моему самый обычный вымышленный 16-разрядный процессор. Нет, это конечно хорошо что народ начал писать эмуляторы, компиляторы, на verilog там что-то делают, да, толчок дали хороший. Но это все — маркетинг, и лучше бы для других процессоров делали то же самое. А то — для AVR эмулятора под linux нет толкового, так чтобы расширять можно было легко и просто. Для PIC кажется тоже. Для STM8 очень классных и модных — вообще ничего нет, даже ассемблера! Но все пишут и пишут для практически непригодного DCPU-16. На этом фоне эмулятор Cortex на AVR выглядит намного круче, хотя шума о нем меньше.

Ну ладно, разворчался я что-то. Читать далее

adk-libusb = adk+libusb

Сделал вот крохотную библиотечку. Любителям андроида и железок должно понравится.

Если вы еще не слышали про ADK (Android Open Accessory Development Kit), то есть неплохая презентация с прошлогоднего Google IO 2011. Там бравые дяди в юбках и очках рассказывают и показывают что это и зачем этот ADK нужен. Читать далее

Android+SDL: Будь мужиком, пиши на C!

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

Я никогда не работал с SDL, но мне кажется, что он очень удобен для написания игр. По крайней мере я бы купился на его кросс-платформенность. Тем более, что теперь в списке его платформ еще и Android. Читать далее

Lua за 60 минут

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

Lua? Что это?

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

Зачем?

Lua может вам пригодится:

* если вы геймер (плагины для World of Warcraft и множества других игр)
* если вы пишете игры (очень часто в играх движок пишут на C/C++, а AI — на Lua)
* если вы системный программист (на Lua можно писать плагины для nmap, wireshark, nginx и других утилит)
* если вы embedded-разработчик (Lua очень быстрый, компактный и требует очень мало ресурсов) Читать далее