?

Log in

No account? Create an account

Программистский вопрос залу - Общество дровосеков Бердичева по изучению Мишны

Nov. 16th, 2010

12:37 pm - Программистский вопрос залу

Previous Entry Share Next Entry



У меня нет под рукой свежих Си-компиляторов (а если бы и были, то только GCC); кто-нибудь может проверить, умеет ли какой-нибудь компилятор находить в этом коде loop invariants и выносить их из цикла, чтобы в нем не оставалось условных переходов?

extern int f(int, int), g(int, int);
int foo(int en, int d1, int d2) {
    int i, s = 0;

    for (i = 0; i < 100; i++) {
        s += en & 1 ? f(d1, i) : g(d2, i);
        s += en & 2 ? f(d1, i+1) : g(d2, i+1);
        s += en & 4 ? f(d1, i+2) : g(d2, i+2);
        s += en & 8 ? f(d1, i+3) : g(d2, i+3);
...
    }
    return s;
}
Но не по-идиотски, репликацией тела цикла (потому что таких условных операторов может быть много, на все экспоненциально не напасешься - GCC, который у меня, например, реплицирует, если в цикле не более 3 условных операторов, а потом вообще ничего никуда не выносит), а введением дополнительных переменных, наподобие
int d_0 = en & 1 ? d1 : d2;
int d_1 = en & 2 ? d1 : d2;
...
int (*fn_0)(int, int) = en & 1 ? f : g;
int (*fn_1)(int, int) = en & 2 ? f : g;

...
for (i = 0; i < 100; i++) {
    s += fn_0(d_0, i);
    s += fn_1(d_1, i+1);
   ...
}
Как бы вы анализировали граф на предмет поиска подобных возможностей?

Comments:

[User Picture]
From:oldjackaroo
Date:November 16th, 2010 09:22 pm (UTC)
(Link)
MSVC 2008 (compiler version 9.0) не умеет.
(Reply) (Thread)
[User Picture]
From:motto
Date:November 16th, 2010 10:01 pm (UTC)
(Link)
clang -v
Apple clang version 1.5 (tags/Apple/clang-60)
Target: i386-apple-darwin10
Thread model: posix

clang -flto -emit-llvm -O3 -S test.c -o temp.asm

http://pastebin.com/hziUWNWq

Такое впечатление, что это именно оно (я могу быть сильно неправ, конечно
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 16th, 2010 10:14 pm (UTC)
(Link)
Увы, там ветвления-схождения хорошо видны (см. %preds), да и явные f/g в вызовах есть. Меня, собственно, реализации для конвенциональных процессоров интересуют постольку-поскольку - чтобы выяснить, озаботился ли кто-нибудь уже этой оптимизацией, и если да, то как ее звать (я придумал deep structure loop invariant optimization; гугление показало, что я сильно неправ).

Чтобы не смущать бедные оптимизаторы, заточенные под процессоры, в которых хорошо предсказанный условный переход + статический вызов дешевле, чем безусловный динамический вызов, можно все вызовы g заменить на f, но и это не помогает.
(Reply) (Parent) (Thread)
[User Picture]
From:motto
Date:November 16th, 2010 10:25 pm (UTC)
(Link)
Теоретически кланг умеет что-то дожимать своим линкером на -о4, практически, конечно, мало шансов

С другой стороны Тутубалин в свое время на реальном проекте получил довольно впечатляющие результаты против gcc
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 16th, 2010 11:02 pm (UTC)
(Link)
Конечно, если вызовов foo мало, и все с константами в качестве en, то можно и при линковке соптимизировать, но меня интересует исключительно преобразование дерева: есть ли какие-нибудь наработки, как собирать инварианты из листьев или отдельных "веток", а не из поддеревьев, как обычно.
Оптимизация получается, если неинвариантные куски ветвей по разные стороны условия оказываются идентичными; выходит, что нужно делать распознавание инвариантов цикла; поиск общих (взаимоисключенных управлением! в отличие от обычного CSE) подвыражений, игнорируя инварианты в них; и схлопывание подвыражений с вынесением выбора инвариантов из цикла.

Мешки ворочать недобродетельно, потому сначала и спрашиваю - может, кто где сделал уже.


Edited at 2010-11-16 11:02 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:alextutubalin
Date:November 17th, 2010 06:58 am (UTC)
(Link)
поиск фамилии по блогам - работает!

Надо понимать, что за код мне оптимизировал clang. То есть там все упиралось в pow() и если просто был подставлен хороший библиотечный (встроенный,точнее) аналог, а не из libm и не из вызова сопроцессора, то в данной конкретной строчке (которая зовется на все пиксели изображения) мог быть выигрыш просто в разы.

Но я не разбирался в деталях, там в этой lcms такой овер-инжиниринг, что она мне накуй не упала, это место будет аккуратно сделано руками когда до него дойдет.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 17th, 2010 07:05 am (UTC)
(Link)
там все упиралось в pow()

Это случайно был не индусский код? А то я видал много любителей писать pow(2, i) для i в пределах 32 или 64.
(Reply) (Parent) (Thread)
[User Picture]
From:alextutubalin
Date:November 17th, 2010 07:23 am (UTC)
(Link)
Не, Marti Maria вроде не индийское имя :)

Конкретно в этом месте - гамма-коррекция (-преобразование) картинки - pow() по смыслу очень даже. И степень дробная (как правило) и возводимое - float.

Другой вопрос, что библиотечное pow() - это ужас нах, особенно если для 25-мегапиксельной картинки его позвать 75 миллионов раз (потому что RGB).

И если в llvm есть свой хороший builtin, то выигрыш мог быть ровно по этой причине.
Хотя в данной задаче нужен не "хороший", а "приближенный" и диапазон входных значений 0..1, что дает еще выигрыш в разы, если не на порядок (для конкретной строчки).
(Reply) (Parent) (Thread)
[User Picture]
From:motto
Date:November 17th, 2010 09:06 am (UTC)
(Link)
Не похоже. То есть там есть какой-то libstdc++ но он так же сбоку, как и отладчик с линкером:

-rwxr-xr-x 1 motto staff 8,5K 17 ноя 11:43 pclng.out
-rwxr-xr-x 1 motto staff 8,5K 17 ноя 11:42 pgcc.out
-rw-r--r--@ 1 motto staff 74B 17 ноя 11:42 ppc.c

otool -L pclng.out
pclng.out:
/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 125.2.1)
tmp motto$ otool -L pgcc.out
pgcc.out:
/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 125.2.1)

Ну и:

Ltmp1:
subq $32, %rsp
Ltmp2:
movl $0, -4(%rbp)
movsd LCPI1_0(%rip), %xmm0
movsd LCPI1_1(%rip), %xmm1
movsd %xmm0, -24(%rbp)
movapd %xmm1, %xmm0
movsd -24(%rbp), %xmm1
callq _pow
(Reply) (Parent) (Thread)
[User Picture]
From:alextutubalin
Date:November 17th, 2010 09:19 am (UTC)
(Link)
Ну значит нет.

В любом случае, компилятор соптимизировал место, от которого лично меня просто стошнило. Может быть gcc - тоже, а llvm менее брезгливый?

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

И, соответственно, оптимизировать ужас бессмысленно, его надо переделывать, толку будет больше.
(Reply) (Parent) (Thread)
From:rezkiy
Date:November 16th, 2010 10:23 pm (UTC)
(Link)
а разве бранч предиктор после пары итераций не рюхнет, кого где вызовут?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 16th, 2010 10:38 pm (UTC)
(Link)
В идеале - рюхнет, но у его кеша размер ограниченный, так что чем меньше мучать предиктор, тем лучше. Да и если вынести выбор между d1 и d2 из цикла, регистры будет легче назначать.
(Reply) (Parent) (Thread)
From:rezkiy
Date:November 16th, 2010 11:37 pm (UTC)
(Link)
Если внутри у функций f(), g() или foo() есть баффер оверран, то подобная оптимизация дает еще один вектор для атаки.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 16th, 2010 11:53 pm (UTC)
(Link)
Что значит "еще один вектор" (я не в курсе терминологии)?

По-моему, чем более вариативен размер фрейма в зависимости от режимов оптимизации, тем меньше вероятность успешной атаки.
(Reply) (Parent) (Thread)
[User Picture]
From:dvv
Date:November 17th, 2010 03:23 am (UTC)
(Link)
Это значит, что если это не типо жава с тотальным рантайм контролем за всем, то мы все умрём.
(Reply) (Parent) (Thread)
From:rezkiy
Date:November 17th, 2010 04:00 am (UTC)
(Link)
ну как... В чем главная опасность оверранов на стеке -- в том, что злоумышленники перепишут адрес возврата и удачно попадут в функцию которая скачает эксплойт. А тут помимо адреса возврата появляются стотыщ интересных переменных, и если попасть в любую из них, то эффект примерно аналогичен. Ну то есть вот буфер, так получилось что он лежит прямо перед адресом возврата; перелетели, привет. Если он лежит не прямо перед адресом возврата, а между ними еще какой-нить указатель, то не факт, что прокатит, потому что ты этот указатель попортишь, оно прямо тут в функции и грохнется. Если на фрейме есть куча таких переменных как fn_Х, можно вместо адреса возврата загадить их, эффект будет примерно такой же, и кука (которое положики на стек в прологе и проверяют в эпилоге перед тем как сделать рет) уже не спасет.

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

Причем тут размер фрейма, я честно говоря не понял.

Ясное дело, что если код без ошибок, то ничего этого не надо, но где вы видели код без ошибок?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 17th, 2010 04:26 am (UTC)
(Link)
Если по адресу в коде эксплойта перейдут не командой возврата, как предполагал автор, а командой вызова, то данные, которые передадутся функции, окажутся не те, которые нужно, и эксплойт не сработает.

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

Впрочем, все это уводит от темы. Я-то Верилог компилирую, мне все эти эксплойты и оверраны до лампочки.
(Reply) (Parent) (Thread)
From:rezkiy
Date:November 17th, 2010 06:52 am (UTC)
(Link)
Все правильно, с той только разницей, что в обычном софтвере злоумышленник всегда прекрасно представляет себе устройство фрейма (бинарник есть, отладчик есть, что еще надо?), и наличие команд вызова никак не мешает ему поиграться с командой возврата, И добавляет команды вызова.

Это и есть новый вектор атаки про который я пишал выше, причем такой вектор который нельзя mitigate куками.

Я не знаю верилога вообще, но подозреваю, что там еть свой собственный класс секурити дыр. Берем малформд код, исполняем, и внезапно часть кода исполняется как будто в режиме ядра.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 17th, 2010 07:29 am (UTC)
(Link)
внезапно часть кода исполняется как будто в режиме ядра.

Это вряд ли. :)
(Reply) (Parent) (Thread)
From:rezkiy
Date:November 17th, 2010 07:31 am (UTC)
(Link)
ну и хорошо, буду спать спокойно. А от темы ушло, потому что я стал рассказывать про то, что такое вектор атаки.
(Reply) (Parent) (Thread)