LINUX.ORG.RU

[C] Изменение кода в рантайме

 


0

0

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

#include <string.h>
#include <stdio.h>

typedef int (*Func)(void);

#ifdef PATCH
char buf[1024];
#define func   ((Func)buf)
#else
Func func;
#endif

int f1(void) { return 1; }
int f2(void) { return 2; }
int f_(void) { return 0; }

int main(void)
{
	int i, sum = 0;
#ifdef PATCH
	memcpy(buf, f2, (char *)f_ - (char *)f2);
#else
	func = f2;
#endif
	for(i = 0; i != 0xFFFFFFF; ++i)
		sum += func();
	printf("sum = %d\n", sum);
	return 0;
}
Действительно, разница значительна:
$ cc -O2 main.c && time ./a.out
sum = 536870910
 
real    0m1.353s
user    0m1.350s
sys     0m0.010s
$ cc -O2 -DPATCH main.c && time ./a.out
sum = 536870910
 
real    0m0.968s
user    0m0.960s
sys     0m0.000s
Сам вижу проблемы:

1. размер функции не определить в общем случае надежно;

2. buf может оказаться неисполняемым.

Можно как-нибудь обойти эти проблемы? Еще лучше, есть стандартные решения для подобных хаков?

★★★★

Последнее исправление: unsigned (всего исправлений: 1)

Можно как-нибудь обойти эти проблемы?

Да

Еще лучше, есть стандартные решения для подобных хаков?

Стандартный «хак» — это не «хак».

Rzhepish
()

Действительно, разница значительна:

Молодец, а теперь потестируй или просто посчитай, насколько изменится профит в случае увеличения тела функции в 25 раз.

Rzhepish
()
Ответ на: комментарий от Rzhepish

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

Если так проще - считай, что интерес академический.

unsigned ★★★★
() автор топика

Лучше алгоритм меняй, чем такими ужасами заниматься.
Простая истина от К.О.: быстрая сортировка на какой-нибудь жабе будет работать быстрее, чем сортировка пузырьком, написанная на ассемблере с 100500 глубокомысленных оптимизаций под данный процессор.

anonymous
()
Ответ на: комментарий от unsigned

каждая миллисекунда.

Сколько комманд выполнит процессор с 5-ти стадийным пайплайном, работающим на частоте 1ггц за 1 миллисекунду?

Rzhepish
()

Ребята, я знаю о вреде неправильных микрооптимизаций, и обещаю их не применять. Неправильные.

Все, что меня сейчас интересует - есть ли устоявшаяся практика решения конкретной задачи.

Если есть - я изучу/замеряю/еще раз подумаю. Если нет - придется, возможно, менять алгоритмы. На менее гибкие.

unsigned ★★★★
() автор топика

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

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

Вообще нужная функциональность называется relocation и она уже реализована в ld.so — когда подгружается, допустим, разделяемая библиотека, то адрес функции в ней подставляется в «jmp .....» в образе программы. Для разных вариантов инструкций, разных адресов и фаз луны есть свои типы релокаций — прочесть про них про всех можно в спецификации целевого ABI.

Вопрос — можно ли эту функцию загрузчика дергать руками (то есть без непосредственно dlopen).

В крайнем случае, если писать руками, то руками писать надо именно relocations из ld.so.

Hope that makes sense.

anonymous
()
Ответ на: комментарий от anonymous

icc генерирует несколько вариантов кода и выбирает нужный (или не очень) при запуске

Это зачем такое и что это за варианты кода?

anonymous
()
Ответ на: комментарий от anonymous

Это зачем такое и что это за варианты кода?

Например, две версии цикла — для процессоров с поддержкой avx и для процессоров без нее.

anonymous
()

этим в основном всякие вирусы и другая малварь пользуется. Вообще с т.з. безопасности память, занятая кодом, должна быть read-only, а память данных должна быть неисполняемой, чтобы такие фокусы не прокатывали

Harald ★★★★★
()

Допустим, вызов происходит на критическом по производительности участке - тогда расходы на вызов по указателю нежелательны.

А что, вызов по указателю дороже чем обычный?

Galant
()

И то что у тебя call дороже самой функции, возвращающей циферку, это только твоя проблема. В реале call должен почти раствориться с учетом конвеера процессора.

Galant
()

buf может оказаться неисполняемым.

Изобретай велосипед^Wвиртмашину @ исполняй бинарные дампы

П.С. настройку памяти (и соответственно обход NX-бита) можешь нарыть в гуглу «Android but not paranoid», как-то так... Где-то тут http://androidbutnotparanoid.blogspot.com/. Но рецепт тебе уже подсказали [C] Изменение кода в рантайме (комментарий)

slackwarrior ★★★★★
()
Ответ на: комментарий от Galant

А что, вызов по указателю дороже чем обычный?

Если указатель в регистре — то скорее нет (mov ip,imm против mov ip,reg — на x86 так написать нельзя, но смысл (и стоимость) от этого не меняется).

Но у ТС указатель хранится в .data (определен в глобальной области видимости), и перед использованием должен быть загружен оттуда.

Реально gcc -O2 генерирует следующее:

.L8:
	movq	func(%rip), %rax
.L6:
	call	*%rax
	addl	%eax, %ebp
	subl	$1, %ebx
	jne	.L8
anonymous
()
Ответ на: комментарий от anonymous

Легче тогда пропатчить call в цикле, а не копировать функцию.
Но разницы в реале, с более тяжелой функцией внутри цикла, не будет практически.

Galant
()
Ответ на: комментарий от Galant

Легче тогда пропатчить call в цикле

Конечно, патчить. :-) Вопрос как раз в том — как это делать наиболее изящно, учитывая при то, что, как я уже говорил, этот код уже написан в ld.so

Но разницы в реале, с более тяжелой функцией внутри цикла, не будет практически.

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

anonymous
()
Ответ на: комментарий от unsigned

Пойдет, но linux-only

Нет, в общем-то.

$ man 2 mprotect | grep -A1 ^CONFORMING
CONFORMING TO
       SVr4, POSIX.1-2001.  POSIX says that the behavior of mprotect() is unspecified if it is applied to a region of memory that was not obtained via mmap(2).
anonymous
()
Ответ на: комментарий от anonymous

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

По-моему, того же самое я могу получить с помощью dlopen.

Я именно от косвенности хочу избавиться, а для этого нужно патчить прямо инструкцию call. Наверно, в ассемблере это несложно, но я ищу решение для C, поэтому «патчить» приходится всю функцию целиком.

unsigned ★★★★
() автор топика
Ответ на: комментарий от anonymous
.L8:
	movq	func(%rip), %rax
.L6:
	call	*%rax
	addl	%eax, %ebp
	subl	$1, %ebx
	jne	.L8

Еще бы, кстати, помогло избавление от перезагрузки регистра адресом функции. Вроде помогает __attribute__((const)), но вообще-то функция может и не быть чистой, а указания «функция не изменяет переменную func» даже в GNU C нет, к сожалению )

Хотя это уже другие оптимизации.

unsigned ★★★★
() автор топика
Ответ на: комментарий от unsigned

это не подойдет, ибо там тоже используется косвенный переход через таблицу

есть разные виды релокаций. в частности, есть и такие, которые переписывают непосредственный адрес в инструкции.

из си, действительно, руками это сделать сложно — поэтому я и призываю посмотреть, как это работает у gcc и ld.so

anonymous
()
Ответ на: комментарий от slackwarrior

За ссылку спасибо, но с кодогенерацией мне все ясно. Мне же нужно изменить свойства статично выделенной памяти, и mprotect здесь поможет, но только на linux.

unsigned ★★★★
() автор топика
Ответ на: комментарий от unsigned

Только в рантайме определится, какую функцию вызывать.

Ну и кто тебе мешает определить, какой код будет выполняться, за пределами цикла в рантайме?

Ты ведь этого хотел:

Допустим, вызов происходит на критическом по производительности участке - тогда расходы на вызов по указателю нежелательны.

?

Рождается трюк, идея:

Твоя «идея» сам вызов функции сохраняет в целости и сохранности, если ты вдруг не понял. Разница же между вызовом по указателю и вызовом по константному адресу по сравнению с ценой самого вызова ничтожно мала.

При условии

тело существенно не увеличится

надо убирать сам вызов, а не пытаться «оптимизировать» его способ.

LamerOk ★★★★★
()
Ответ на: комментарий от anonymous

есть и такие, которые переписывают непосредственный адрес в инструкции.

Я не знаток, но по-моему, это невозможно хотя бы потому, что .text недоступен на запись. Этим и объяснялась необходимость отдельной таблицы в какой-то статье по линковке.

unsigned ★★★★
() автор топика

А что, предсказание банального if-a по выбору ф-ии (инлайновой) уже отменили? Или я чего то не понимаю?

AIv ★★★★★
()

С -DPATCH тоже сегфолтится, но система 32-битная.

[pf@eternity]:[~][0]% cat /proc/cpuinfo | grep model\ name | head -n 1
model name	: Intel(R) Pentium(R) Dual  CPU  T2330  @ 1.60GHz
[pf@eternity]:[~][0]% cat /proc/cpuinfo | grep flags | head -n 1
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm dts
[pf@eternity]:[~][0]% uname -a
Linux eternity 3.1.4-pf #1 SMP PREEMPT Sun Dec 4 18:39:42 EET 2011 i686 Intel(R) Pentium(R) Dual CPU T2330 @ 1.60GHz GenuineIntel GNU/Linux
post-factum ★★★★★
()

1. размер функции не определить в общем случае надежно;

А нафига ее копировать? Изменяй адрес перехода в соответствующей команде call

2. buf может оказаться неисполняемым.

Ну так выдели буффер, в котором исполнение разрешено. mmap тебе в помощь

AF ★★★
()
Ответ на: комментарий от AIv

А что, предсказание банального if-a по выбору ф-ии (инлайновой) уже отменили?

А если условное выражение невычислимо во время компиляции?

no-such-file ★★★★★
()

И это, самое главное, ты свой buf всеравно через указатель на функцию вызваешь

AF ★★★
()

А если так:

#include <string.h>
#include <stdio.h>

typedef int (*Func)(void);


int f1(void) { return 1; }
int f2(void) { return 2; }
int f_(void) { return 0; }

int main(void)
{
int i, sum = 0;

const Func const func = f2;

for(i = 0; i != 0xFFFFFFF; ++i)
sum += func();
printf("sum = %d\n", sum);
return 0;
}

результат gcc -S -O2

main:
.LFB26:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	andl	$-16, %esp
	subl	$16, %esp
	movl	$536870910, 4(%esp)
	movl	$.LC0, (%esp)
	call	printf
	xorl	%eax, %eax
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
no-such-file ★★★★★
()
Ответ на: комментарий от AF

не, не так. int a1[10] и int* a2 отличаются принципиально. Так и с функциями и указателями на функции.

anonymous
()
Ответ на: комментарий от no-such-file

Сейчас глянул вариант с Func func=f2. Генерирует просто call f2 без всяких заморочек.

no-such-file ★★★★★
()
Ответ на: комментарий от unsigned

Именно об этом и говорю: моя память получена не от mmap.

Выделить буфер через mmap религия запрещает?

Deleted
()
Ответ на: комментарий от no-such-file

А что, предсказание банального if-a по выбору ф-ии (инлайновой) уже отменили?

А если условное выражение невычислимо во время компиляции?

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

AIv ★★★★★
()

Я бы вызывал разные куски кода с циклом for, в которых статически вызываются нужные f[_12], а в месте, где у тебя патч, написал бы if или switch, который и решает, какой цикл будет исполняться. Т.е. решение о вызове нужного куска принимать на более высоком уровне. В таком случае, функции можно будет заинлайнить.

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

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

anonymous
()
Ответ на: комментарий от LamerOk

Разница же между вызовом по указателю и вызовом по константному адресу по сравнению с ценой самого вызова ничтожно мала.

Только эта разница меня и волновала (как показано в ОП, порядка 40% на инструкцию - а это кое-что). Да, я знаю, что в общем это очень мало и может остаться незамеченным. Я этим занялся больше из интереса.

надо убирать сам вызов, а не пытаться «оптимизировать» его способ.

Нельзя убрать вызов - функций несколько на выбор. Это бы значило встраивать саму функцию по месту вызова в рантайме, а на C такое не сделаешь.

unsigned ★★★★
() автор топика
Ответ на: комментарий от post-factum

С -DPATCH тоже сегфолтится, но система 32-битная.

Благодаря PAE, видимо.

unsigned ★★★★
() автор топика
Ответ на: комментарий от AF

Изменяй адрес перехода в соответствующей команде call

В C нет инструкции call.

mmap тебе в помощь

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

ты свой buf всеравно через указатель на функцию вызваешь

Нет.

unsigned ★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.