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. Но, конечно, свой велосипед ближе к телу.

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

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

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

adk-libusb = adk+libusb

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

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

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

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

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

addr2line, или Мне стыдно

Статья будет очень короткой.
Я столько лет писал и отлаживал, но даже и не знал о таком инструменте. А штука полезная, если неохота лезть в gdb.

Пишем глючную программу

Вот пример нерабочей программы:

void f() {
	int *p = 0x12345; /* Invalid address */
	*p = 5;
}

int main() {
	f();
	return 0;
}

Ошибка, естественно в 3-й строке. Но допустим мы ее не заметили. Соберем отладочный и релизный бинарники, например таким Makefile:

all: debug release

debug:
	gcc main.c -g -o main.debug

release:
	gcc main.c -o main.release
	strip main.release

Ааа! У меня ничего не работает!

Пользователь говорит, что ваша программа падает с загадочным segmentation fault. Но мы не боимся, и наша логика теперь простая.

Во-первых, смотрим вывод dmesg:

$ ./main.release
zsh: segmentation fault  ./main.release
$ dmesg | tail
....
[90461.350925] main.release[21028]: segfault at 12345 ip 00000000004004f4 sp 00007fffe640ce10 error 6 in main.release[400000+1000]

Вот мы узнали адрес, на котором произошел вылет — 0x00000000004004f4

И тут на арену выходит addr2line, которая по этому адресу и дебажному бинарнику говорит нам где ошибка:

$ addr2line -e main.debug 0x00000000004004f4                                                                                                          
/tmp/addr/main.c:3

Вот и все. Исправляем ошибку в третей строчке в файле main.c. Круто, правда?

Как легко портировать ассемблер на примере Chip8

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

Почему? Потому что хочется если уж ассемблер, то макросы. А лучше над ассемблером сразу C или еще что покруче. А ассемблер у нас детский, и крэшится при каждой строчке с неправильным синтаксисом. А хочется настоящего. Читать далее

PDP-11. История рядом.

Если вы юниксоид, вы наверняка слышали о PDP-11. Если вам меньше 40 лет, то вы почти наверняка их не видели. Для тех представителей нового поколения, которые выбирают Unix, добрые люди написали эмулятор старого железа — SIMH. Читать далее