Оптимизация и полиморфный код

Полиморфный код удобно использовать в вирусах, механизмах защиты прог. от копирования, и как ни странно для оптимизации. По крайней мере это относится к процам архитектуры IA32(x86). Использование полиморфного кода для них позволяет существенно экономить регистры общего назначения. Использовать эту оптимизацию я начал при создании утилиты WGC (аналог Artmoney & TSearch). Задача ставилась такая: как можно быстрее находить вхождения образца в некоторый буффер, используя тип значения и условия поиска (типа > < = !=). Писать отдельные функции на каждый вариант поиска меня не устраивало, поэтому я решил сделать одну полиморфную функцию. Перед началом цикла поиска/отсева изменялись команды сравнения, условного перехода и адресации.

Адресоваться к динамически выделенному буфферу, используя косвенную адресацию типа: mov ecx, [edi + eax] при дефиците регистров я не стал. Записал просто mov ecx, [eax + 12345678h], а перед циклом число 12345678h заменял на адрес буффера, таким образом экономя регистр.

В настоящий момент программа до конца не оптимизирована, но даже не смотря на это поиск достигает 120Mb/s (на Athlon 2000+@1666;512DDR333) , включая упаковку найденых смещений, выделение буферов памяти. Собираюсь развернуть циклы в скором времени.

Что бы не было исключительных ситуаций при записи в область кода, ее приходится разрешать для записи функцией VirtualProtect.

 

а где вопрос? или это просто информация к сведению?

 

Точнее было бы назвать это не полиморфизмом, а небольшой самомодификацией, IMHO

 

>2 Funbit

просто информация, сам я в поисках инфы по этой теме никуда не ушел. Надеюсь кто поопытнее поделится своим опытом оптимизации в условиях ограниченых ресурсов ЦП.

> B_108

можно и так назвать, мне важен результ.



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

 

Вот что пишет сам производитель процессора:



AMD Athlon™ Processor x86 Code Optimization Guide

У intel тоже самое.



(Кстати, многие компиляторы вопреки этому правилу помещают jump table для switch вблизи самого перехода..)





>

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





Ещё, более компактный код вроде



mov ecx, [edi + eax]



будет в некоторых случаях работать быстрее, чем



mov ecx, [eax + 12345678h]





Если кажется что мало регистров, можно использовать EBP и ESP для хранения данных.

А так же MMX - последними и поиск иногда делать удобнее.







>

Можно задать атрибут записи для секции кода при линковке.





Скорость чтения памяти Athlon 2000+@1666 на DDR 266 1350Mb/s; на DDR333 думаю столько же будет, тест в аттаче.

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

_1698994866__read_test.exe

 

2> S_T_A_S_

Действительно можно: имеем следующее количество функций для (BYTE, WORD, DWORD) x (> < = <> >= <=) т. е. 18 реализаций функций. В коде это относительно мало, но не позволяет использовать ассемблерные вставки (если "размножить" текст - его тяжело будет потом изменять), т. е. придется использовать асм и макросы.

Цикл обычно выполняется для буффера в 64К. Затраты на самомодификацию - примерно по 300 тактов на каждое изменение кода, а их у меня бывает от 3 до 5, значит максимальный проигрыш 1500 тактов. Если ведется поиск в процессе на 64Мб, всего будет проиграно 1,5 млн. тактов - не очень заметно по сравнению с другими потерями. Если же в программе один запрос или

запросы по критериям одинаковы, модификацию кода можно выполнить перед началом поиска/отсева.

Хорошо бы, но практика показала другое. У последнего варинта кода время выполнения было немного меньше чем у первого.

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

Не пробывал, для Delphi я использовал то что знал на тот момент.

Здесь ограничители другие: ReadProcessMemory в частности и GetMem/FreeMem. Покрайней мере если я комментирую функцию поиска, скорость возрастает аж до 250Mb/s. С другой стороны и в самом деле задел просто огромный, простую оптимизацию я посути не выполнял вообще. Особенно медленно должен выполнятся поиск значений DWORD - при инкременте указателя на 1 не раз пересекаются границы кэш линеек. В принципе можно и отказаться от инкремента на 1 - но вполне вероятно что в играх значения могут быть не выровнеными.

 

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

2143469732__ChAlgs.zip

 

[offtop]

S_T_A_S_ аттач не грузиться на w2ksp4 , Exception C000012D (COMMITMENT LIMIT) , что это может значить ?

 

alpet >

Я имел ввиду при запуске программы, выделить память с PAGE_EXECUTE и туда скопировать один код 18 раз, а потом каждый вариант подправить 1 раз и вызывать именно эти кусочки.

2е правило оптимизации - выносим всё что можно за циклы





>

Вообще в теории, время выполнения этих команд одинаково. В той же теории рекомендуется использовать команды, размер опкодов которых меньше - это лучше для декодера. На практике же результат будет зависеть больше от других факторов - от выравнивания циклов, располагается ли опкод на пересечении границ строк кеша или нет. Так что если не учитывать эти факторы, то результаты могут расходиться с теорией. Существует хорошая тулза для анализа таких вещей AMD CodeAnalyst, но для програм на Delphi она будет бесполезна..

Не уверен, что в Delphi вообще возможно как-то повлиять на секции PE файла, так что VirtualProtect тут вполне логично. Вариант - заюзать PE tools и исправить атрибуты у готового exe, но это не удобно.





>

В некоторых случаях оптимизацию делать совсем бессмысленно (разве что для получения опыта) - т.к. тормоза совсем в другом месте - API никогда не отличалось скоростью. GetMem/FreeMem - это что-то из delphi ?





>

IMHO это один из лучших возможных способов увеличить скорость особо не напрягаясь.

Все нормальные компиляторы будут располагать данные выровненными по их размеру.





По поводу кода. лучше избегать команд вроде lodsw, разкладывая их на составляющие. Тем более в таких местах:

Код (Text):

1.  
2.     lodsw
3.     movzx         eax, ax

Деление заменять умножением

Код (Text):

1.     xor           edx, edx       // Подготовка к делению edx:eax / 10
2.     div           ecx            // V = V / 10
3.  
4.  
5. MagicNumber = 3435973837
6. mov eax,X
7. mov edx, MagicNumber
8. mul edx
9. SHR edx, 3

Так же pop лучше вообще по возможности избегать - медленно.





Если нужна скорость IMHO лучше не делать универсальную ф-цию для поиска byte/word/dword - специализированные варианты могут работать в разы быстрее иза-распараллеливания. См. Сравнение одним махом







bogrus

Интересно.. w2k Без SP работает. Наверное не нравится, что VirtualSize у секции кода слишком большой.

Переделал, теперь есть вариант с VirtualAlloc (сорри, сорцы наспех выдраны из другого места)

_1750614076__2.zip

 

S_T_A_S_

Да действительно , начал его менять 00F01000 - не хочет , 00201000 - выдало "типа свободная виртуальная память заканчиваеться , будет увеличена ..." и заработала , потом снова 00F01000 - работает , а 06001000 не хочет . Видимо от размера свопа зависит .

 

S_T_A_S_

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

1. Использовать как можно реже, в идеале копировать память за раз (это правда нереально из-за фрагментированности виртуальной памяти процесса и физической компа). Не достаток - программа будет "зависать" на время копирования, и наверное потребуется физическая память для копирования между процессами, размером равная копируемым регионам.

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

 

GetMem/FreeMem & New/Delete управляют в Delphi кучей. Быстро, но не идеально, при чем иногда наблюдается рост занимаемой программой памяти (это зависит чисто от Windows), хотя внутри проги все высвобождается вовремя.

Идеи как написать свой менеджер памяти у меня есть, и в нем я тоже думаю применить динамический код.

 

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

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

 

Похоже что для указаного кода, есть решение без потери тактов. Штрафные такты ведь возникают при остановках конвейера, после каждой попытке записи в область кода. Областью кода при этом считается, все что попало в кодовый кэш L1. Значит если модификация производится до выполнения функции (т.е. ее код отсутсвует в L1), процу не надо будет сбрасывать конвейер - он отнесется к коду, как к данным. Возникает задача - после модификации код надо вытеснить из L1.DATA кэша в L2, что бы оттуда он загрузился, при вызове функции, в L1.CODE. Для процессоров AMD Athlon c exlusiv'ной архитектурой кеш памяти, это проблем не представляет, надо просто забить L1.DATA.

 

По read_test.exe. Сейчас мне до Athlona не добраться, проверил на iCel2400: макс. результат - 1605Ms/s. Скорость поиска колеблется от 100 до 115Мб/с.

 

alpet

А она(другая процессорная архитектура) уже неплохо

вырисовывается. Т.е. нужен процессор, где были бы

флажки для модификации выполняемых сходных команд.

Т.е. в твоем случае понадобилось бы не переписывать

коды команд, а просто поставить нужные флажки.

В идеале можно было сделать программирование

с минимумом переходов, т.к. программа была бы

почти линейной, ну кроме циклов конечно.

 

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



А неплохо бы было иметь набор программируемых инструкций. Можно было бы получить код типа:

Код (Text):

1.  
2.  setinstr 80h, 01h  ; dmov копирует байты
3.  setinstr 30h, 01h  ; dcmp сравнивает однобайтные значения
4.  setinstr 78h, 15h  ; dskip префикс пропуска команды, на ZF
5.  
6. @loop:
7.  dmov     rbx, [esi]
8.  dcmp     rax, rbx  ; На самом деле al, bl
9.  dskip jmp    @skip ; Если значения не равны, данная команда будет пропущена
10.   .... ; сохранение адреса
11. @skip:
12.  dinc    esi        ; на 1 в данном случае
13.  cmp     esi, [limit]
14.  jb      @loop
15.  

Весьма компактный и универсальный код бы получился.

 

Если идеально оптимизировать поиск, надо цикл развернуть до 16 раз. Это подходит для алгоритма побитовой упаковки найденых результатов: в два байта умещается 16 смещений.



В теле цикла будет нечто вроде:

Код (Text):

1.  
2.  @loop:  
3.    cmp  ecx, [esi]  ; Сравнить с образцом
4.    sete al          ; Установить в 1 если равно  
5.    or   bl, al
6.    shl  ebx
7.    inc  esi
8.    ... и так 16 раз.
9.    mov  [edi], bx  ; сохранить множество
10.    add  edi, 4
11.    cmp  esi, 12345678h
12.    jb  @loop
13.  

Нет ни jmp'ов, ни call'ов - благодать для конвейера. Для AMD64 цикл соответсвенно можно до 64 раз развернуть, но будут издержки на хвосты буфера, их придется искать отдельно, или забивать значениями не совпадающими с критериями поиска.

 

alpet >

К слову.

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

И это даёт прирост скорости в ~2 раза.

Код из теста конечно далёк от реальности, поскольку ничего полезного не делат, но показывает тот порог, с которого нужно думать о низкоуровневой оптимизации.

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





>

Можно не строить догадки, а проверить.

Например, сравнить 2 варианта поиска байта == 0



A)

mov al,0

rep scasb



B)

\masm32\M32LIB\STRLEN.ASM (см. аттач).



Последний вариант легко адаптируется для поиска любых значений.

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

_1854888455__STRLEN.ASM

 

S_T_A_S_ Использовать цепочечные команды в прнципе можно. Но есть следующие ограничения:

<ol type=1>

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

2. Цепочечные команды допускают поиск значений по критериям "равно", либо "не равно", то есть ограничивается поливариантность поиска.

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

</ol>.



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