Здрасте

Задача следующая, решения пока я не вижу.
Приложение взято под визор/трассировку - не суть важно, имеем каждую инструкцию его.
Исполнение цикла имеет большой тайминг, посему цикл необходимо обнаружить и скипнуть.
Как обнаружить цикл ?

Вначале нужно дать какое то чёткое определение - что такое цикл.
Серия вызовов функции(апи к примеру) очевидно это не цикл.
Можно в графе найти замыкания ветвей, но мы его построить не можем - это слишком долго, нужно всё сделать в динамике.

-----
vx

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

difexacaw
не реально. без статик прогона на loop/etc. или 2-3-n раза каунтер считать на лупбэк. штук хз сколько каунтеров. все имхо

-----
От многой мудрости много скорби, и умножающий знание умножает печаль

| Сообщение посчитали полезным:

ajax пишет: не реально. без статик прогона на loop/etc.

+1. Нормальный софт делает это во время загрузки таргета, а дальше уже работают алгоритмы кэша и оперативная память которую так любят jit компиляторы.

| Сообщение посчитали полезным:

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Может как то накопить в буфере поток инструкций

Не потребуется никакого огромного объема, clr jit жрет память из за того, что он кроме цикла умеет разворачивать код и предсказывать результаты, ему еще приходится собирать статистику по данным ну и GC.
Собрать статистику по jmp\je\jnz, а дальше смотреть на признаки цикла, поиск счетчика и условия, если прыгаем в границах счетчика, значит это цикл, хотя с лапшой это не поможет, например когда прыгает в другую функцию и хз через сколько функций возвращаемся назад.

| Сообщение посчитали полезным:

shellstorm

Код выполняется под визором в реалтайме. Любое связывание с кэше инструкций сделает приложение слишком тормозным и висячим.
И не ясно как определить цикл, в частности вложенный. Может быть вызвана в цикле одна процедура, которая может содержать в себе не повторяющиеся вызовы и циклы. Как найти верхний из этих циклов не понятно. Имея граф можно пройти обратно по ссылкам, найти первичный цикл. Но это нужно сделать без графов. Что и для чего сохранять, ветвления - непонятно %

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Как найти верхний из этих циклов не понятно

Например один из инструментов для intel pin строит call graph во время загрузки таргета, а дальше уже корректирует граф глядя на контекст. Совсем без графов решить можно лишь накоплением статистики, поскольку как уже говорилось, цикл может быть далеко за пределами одной функции и с кучей условий. Копить статистику поглядывая на контекст.

Добавлено спустя 2 минуты
Здесь одного запуска может не хватить, поскольку условия могу зависеть от данных, один раз запустили и нет цикла, а во время другого запуска и с другим набором данным можно полдня крутиться.

| Сообщение посчитали полезным:

shellstorm

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: скипнуть цикл прямым его исполнением

И как ты без счетчика это делать будешь? Нужно брать как минимум адрес перехода и если вернулись к нему сова, возможно это цикл, а совсем без каких то промежуточных данных никак, по крайне мере быстро, можно конечно еще сбегать посмотреть, куда ведет переход, но цепочка может быть длинной в итоге на предпросмотр потратишь гораздо больше времени чем на подготовку промежуточных данных и счетчик.
Граф используется во время загрузки приложения, а не строится во время работы. Посмотри например упрощенную реализацию у pin.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.7096&rep=rep1&type=pdf

| Сообщение посчитали полезным:

shellstorm

Меня метод интересует решения, а не статик костыли как в dbi.

Нужно чёткое определение цикла.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Нужно чёткое определение цикла
его тупо нет. особенно с x64. на возврат делать табличку, приличную, и в статике один фик

-----
От многой мудрости много скорби, и умножающий знание умножает печаль

| Сообщение посчитали полезным:

difexacaw пишет: Нужно чёткое определение цикла

Это тоже из теории графов.
--> Цикл_(теория_графов) <--
Четче уже некуда.

| Сообщение посчитали полезным:

Не вижу никаких в этом проблем.
Вначале нужно дать какое то чёткое определение - что такое цикл.
Повторение пройденного - этого определения вполне достаточно. Хотя первоначально под это определение попадут не только циклы.
Адрес - идентификатор цикла, если адрес уже пройден, то скипаем его и идем по необработанной ещё ветке. Не придется 2 раза анализировать один и тот же код. Для прыжков по любым необработанным веткам на любом переходе (условном/безусловном) сохраняем весь контекст функции (регистры, стек, задействованную память), идентификатор сохранения - адрес перехода. На первом проходе строим табличку переходов и меток (рефов на переход), прошли 1 реф, пометили и больше его уже не проходим, анализ идет до тех пор пока в табличке есть не помеченные рефы. На втором проходе включаем декомпилятору мозги и он уже строит все ветвления как в реале, и только тут можно 100% определить цикл это или просто метка с кучей рефов.
Но зато гарантированно всё будет пройдено и только по одному разу.

-----
Everything is relative...

| Сообщение посчитали полезным:

ajax пишет: его тупо нет. особенно с x64

Да, в некоторых случаях это NP полная задача.

| Сообщение посчитали полезным:

Vamit

Не понимаю, опишите по шагам.

shellstorm

Это определение тут видимо не годится, графа же нет

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

Если после выполнения процедуры к примеру выполнился не известный код и произошёл повторный вызов процедуры, то это не цикл. Иначе это будет цикл.

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

Добавлено спустя 1 час 24 минуты
Нашёл решение в следующем виде.
Ведём буфер, в котором трекаем поток инструкций, при переполнении буфер смещаем на одну запись. При обнаружении адреса в этом буфере начинаем отслеживать поток инструкций, проверяя на совпадение следующую запись в буфере с текущим адресом. Если поток совпадает до следующей итерации цикла, то цикл обнаружен.



Если это решение применить для кода вида:



Получится запись в буфер первого Call, далее поток инструкций R(), следующий Call и повторный вызов R. При этом начнётся отслеживание потока инструкций и так как после возврата из второй процедуры окажется что записи в буфере нет, отслеживание прекратится - это не цикл.

Если применить к такому циклу:



После Jcc начнётся отслеживание потока, которое продлится до следующей итерации(L) - цикл обнаружен.

Но такой метод не обнаружит вложенные циклы.

Добавлено спустя 2 часа 40 минут
Собрал тест.

Для тестовой апи находит системные циклы, помимо строковых инструкций




b965_21.05.2017_EXELAB.rU.tgz - Cycle.rar

-----
vx

| Сообщение посчитали полезным: mak

difexacaw пишет: Это определение тут видимо не годится, графа же нет

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

| Сообщение посчитали полезным:

shellstorm

Из моего определения следует решение. Как ваше определение использовать для данной задачи ?

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Как ваше определение использовать для данной задачи ?

DFS, это получается хоть с графами, хоть с промежуточными данными из контекста и стека.
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BD%D0%B0%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

| Сообщение посчитали полезным:

shellstorm

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Опишите плз как реализовать данные способы в моём случае

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

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

| Сообщение посчитали полезным:

shellstorm

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

Как будет выглядеть непосредственно алгоритм ?

-----
vx

| Сообщение посчитали полезным:

загоняем X и Y в любой удобный список, оба варианта годятся, но в этом случае avl избыточный, неоправданное расточительство, вот на счет самого списка, формат зависит от того, будешь ли ты хранить связи ссылок или будешь каждый раз пересчитывать, первый вариант хоть и немного, но жрет память, а на втором теряем скорость. Вот здесь наглядное описание, просто замени граф на slist или avl и реши что собираешься делать со связями, хранить или пересчитывать, если первое, добавляем к списку дополнительный список связей, если пересчитывать, пилим функцию поиска связей по образу и подобию того, что по линку.
https://neerc.ifmo.ru/wiki/title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD

| Сообщение посчитали полезным:

shellstorm

А когда изменять список, записывать и очищать ?

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: А когда изменять список, записывать и очищать ?

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

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

| Сообщение посчитали полезным:

shellstorm

Подумаю позже со списками. Как цикл лучше выделить в буфер ?

> будем знать о наличии цикла и размере его тела

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Кстате размер тела это размер всех его инструкций, для этого так же никакие связанные списки не нужны

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

| Сообщение посчитали полезным:

shellstorm

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

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: бесполезных ссылок

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

| Сообщение посчитали полезным:

shellstorm

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

-----
vx

| Сообщение посчитали полезным: